§ Вступительный LOGOS

Существует очень большое количество сортировок, по тому количеству, которые существуют, можно написать увесистую книгу размером с кирпич и весом тоже с кирпич, причем одно перечисление всех возможных сортировок только займет страниц пять. Я разберу один из видов сортировки — это сортировка слиянием. Постараюсь разобрать так, чтобы потом самому вспомнить, как он работает.
В чем преимущество такого вида сортировки, так это то, что она в целом то, простая для понимания, а также легко распараллеливается, можно сортировать несколькими потоками, что очень хорошо для например, использования ее на видеокартах, к примеру, бюджетной и недорогой видеокарты NVIDIA RTX 4070 или еще каких-нибудь с маркой PALIT, кто в теме, тот спалит.

§ Примерно как работает

На мгновение представим, что у нас есть неотсортированный массив. Когда представление и визуализация закончена, можно просто написать его для наглядности: 5, 2, 3, 10, 7, 4, 8. Массив содержит в себе 7 элементов и требует хозяйской руки, чтобы его отсортировать. Способов существует тьма-тьмущая, но рассматриваем только сортировку слиянием.
Строго говоря, эта сортировка действует по принципу "дели на две части, пока не поделишь так, что делить будет нечего". Теперь комментируем высказывание, ибо ничего не понятно. Сказано было, что массив надо разделить на две части, причем они могут быть и не равны друг другу по количеству элементов, но все же, надо, чтобы отличались по количеству не более чем на 1 элемент. То есть, если количество элементов, которые мы делим, нечетное, то либо слева будет на один элемент больше, либо справа, это не играет роли.

5, 2, 3, 10, 7, 4, 8
=>
5, 2, 3 | 10, 7, 4, 8

Я разделил надвое массив и получил 3 элемента слева, и 4 элемента справа. В данный момент времени нам это совершенно ничего не дает, потому что деление не завершено до конца. Есть еще что поделить. Теперь делим еще, то есть то что слева получилось сначала делим надвое, и потом то что справа получилось, тоже надвое:

Массив 5 | 2, 3 || 10, 7 | 4, 8
Слот   1 |  2    |   3   | 4

Вот теперь все поделено нормально. А что значит нормально? Это значит, что дальше мы поделить уже не можем, ибо в слотах остался либо 1 элемент, либо 2. Если так получается, то делить уже далее нельзя. Надо сортировать.

§ Сортировка листьев

Начнем сортировку.

• В слоте 1 сортировать ничего не надо, тут уже и так все отсортировано, ибо сортировать один элемент сам с собой бессмысленно — он сам себе хозяин и господин в своем слоте.
• Слот 2 содержит последовательно идущие числа 2 и 3, которые отсортированы правильно, поэтому их тоже пропускаем.
• Слот 3 уже состоит из элементов 10 и 7, которые расположены неправильно, переставляем местами, получается 7 и 10
• Слот 4 тоже отсортировано верно

Теперь получим следующий массив:

5 | 2, 3 || 7, 10 | 4, 8

Дело в том, что каждый слот теперь отсортирован верно, но, слоты надо укрупнить теперь. И как раз вступает в действие принцип MERGE.

§ Слияние отсортированных массивов

Если у нас представлен массив с элементами A1 A2 A3 ... An и массив B1 B2 B3 ... Bn, причем у каждого этого массива все элементы отсортированы по возрастанию (либо по убыванию), то есть алгоритм, который позволяет соединить эти два массива в один отсортированный массив.
Такой метод требует места, потому что слияние массивов невозможно выполнить перестановки хотя бы по той причине, что новый массив должен получится примерно вдвое больше, то есть количество элементов итогового массива будет суммой количества элементов исходных массивов.
Рассмотрим общий алгоритм слияния массива A и массива B.

• Сравниваем элементы A[i] и B[j], если A[i] меньше или равен B[j], то это значит, что все хорошо, добавляем в итоговый массив значение A[0] и так как мы его использовали, то передвигаем указатель i+1 с 0 на 1, если конечно, массив A не состоит из 1 элемента
• Иначе, если A[i] больше чем B[j], то это значит, что надо добавить теперь B[j] вместо A[i] в итоговый массив, и передвинуть указатель j+1 уже у массива B, кроме случая, когда все элементы исчерпаны
• Повторяя так несколько раз, рано или поздно указатели упрутся в конец массива. Если это произойдет, то надо выгрузить остатки элементов у тех, где еще указатель не дошел до конца — они в любом случае будут больше, чем тот массив, который уже закончился

Лучше всего показать на примере. Возьмем два отсортированных массива и создадим из него новый.

i: 0 1 2  3  4 5  -- номер элемента
A: 1 4 6 10 12 13
B: 3 5 7  8 11

Алгоритм

• Сравниваем элементы A[0] и B[0]. В данном случае, элемент A[0]=1, B[0]=3 и первый элемент меньше, чем второй, так что добавляем 1 и теперь далее рассматривается элемент A[1]
• Сравнивается A[1] и B[0], и вот тут A[1]=4, B[0]=3, видно, что B[0] меньше, чем A[1], поэтому добавляем 3 и передвигаем указатель у массива B
• Элемент A[1]=4, B[1]=5, добавляем 4 в итоговый массив, сдвигаем указатель A на +1 вправо
• Элемент A[2]=6, B[1]=5, уже меньше получится B[1], аналогично, добавляется 5, сдвигается указатель B
• Сравнение A[2]=6, B[2]=7, добавляем 6, сдвигаем на A[3]
• Сравнение A[3]=10, B[2]=7, наоборот, теперь добавляется 7, и сдвиг на B[3]
• Аналогично A[3]=10, B[3]=8, снова добавляем 8, сдвиг на B[4]
• Сравнение A[3]=10, B[4]=11 дает то, что добавляется 10 в итоговый массив, сдвиг на A[4]
• Финальное сравнение A[4]=12, B[4]=11 добавляем 11, и сравнения закончены, так как один из концов массива был достигнут
• Остатки массива A выгружаем в итоговый массив, а там осталось число 12 и 13

Итоговый массив будет иметь вид: 1 3 4 6 7 8 10 11 12 13, то есть, полностью отсортированный массив.

§ Сортировка слиянием

Итак, разобрались с алгоритмом слияния отсортированных массивов и как это применить к сортировке? Очень просто. После того, как были отсортированы слоты из 1 или 2 элементов, эти массивы считаются отсортированными по определению, однако, теперь их надо объединять с помощью алгоритма слияния.
5 | 2, 3 || 7, 10 | 4, 8
Берем группы массивов, которые надо объединить, слева направо. Как видно, слева есть группа из двух массивов 5 и 2,3. С помощью слияния, объединяется в другой массив 2,3,5. Вторая группа справа, это массивы 7,10 и массив 4,8. С помощью алгоритма слияния, получается массив 4,7,8,10. Теперь подставим результаты:

5 | 2,3 || 7,10 | 4,8
=>
2,3,5 || 4,7,8,10

Как видим, теперь же получились 2 группы отсортированных по возрастанию массивов. Они не могут быть не отсортированными, потому что слияние двух отсортированных всегда дает другой отсортированный массив.
Применяем опять то же самое слияние для левого и правого массива, получая итоговый массив:

2,3,5 || 4,7,8,10
=>
2,3,4,5,7,8,10

Тем самым получается полностью отсортированный по возрастанию массив методом слияния.