6. Алгоритмы сортировки слиянием (MergeSort)

Эта группа алгоритмов построена на следующей общей идее. Пусть имеются два массива, A₁иA₂, каждый из которых уже отсортирован. Тогда можно выполнить операциюслиянияэтих массивов, результатом которой будет новый массивB, содержащий все элементы изA₁иA₂и при этом тоже сортированный. При этом важно, что процедура слияния может быть выполнена за линейное время, а точнее сказать, число итераций будет равно числу элементовB.

Операция слияния выполняется просто как просмотр массивов A₁иA₂от начала к концу; каждый раз сравнивается пара текущих элементов изA₁иA₂, меньший из них записывается в массивB, после чего индекс в соответствующем массиве увеличивается на 1. Когда достигается конец одного из массивовA₁илиA₂, оставшиеся элементы другого массива переносятся вB.

Но откуда возьмутся сортированные массивы A₁иA₂? От ответа на этот вопрос зависит выбор конкретного алгоритма сортировки слиянием.

Наиболее простой из этих алгоритмов так и называется: сортировка простым слиянием. Он заключается в следующем. Пусть дан произвольный (не сортированный) массивA. Для простоты примем сначала, что число его элементов четно:n = 2m. Каждый элемент изAможет рассматриваться как отдельный массив длиной 1, причем такой «массив», конечно, можно считать сортированным. Будем брать в качестве сливаемых массивовa₁иa_m+1,a₂иa_m+2, …a_mиa_2m. Получающиеся при слиянии упорядоченные пары элементов будем помещать во вспомогательный массивBот его начала.

Теперь возьмем в качестве сливаемых массивов пары элементов из B: (b₁,b₂) и (b_m+1,b_m+2), (b₃,b₄) и (b_m+3,b_m+4), и т.д. Образующиеся упорядоченные четверки элементов будем записывать в массивAот его начала. Затем будем сливать эти четверки в группы по 8 и записывать их вB, и т.д. Через несколько таких проходов длина упорядоченной группы элементов достигнетn, т.е. массив окажется полностью отсортированным.

Все сказанное вполне понятно, если размер исходного массива равен степени 2, поскольку при этом всегда будет образовываться целое число полных групп по 2, 4, 8, 16 и т.д. элементов. При любом ином размере массива часть групп будет неполной, однако это чисто техническое затруднение несущественно, поскольку длина сливаемых массивов не обязана быть одинаковой.

Чтобы оценить эффективность алгоритма, напомним, что число итераций при слиянии двух массивов равно их суммарной длине. Очевидно, что на каждом проходе слияния будет выполняться nитераций. Число проходов тоже нетрудно определить: поскольку длина отсортированных групп удваивается при каждом проходе, то эта длина достигнет значенияnпосле выполненияlog₂nпроходов. Отсюда следует, что время сортировкиT(n) = O(n·log(n)), причем эта оценка справедлива как для среднего, так и максимального времени сортировки. Таким образом, алгоритмы слияния являются другим видом алгоритмов сортировки (помимо пирамидальной сортировки), которые гарантируют время порядкаn·log(n)даже в худшем случае.

К сожалению, алгоритмы слияния имеют существенный и неустранимый недостаток. Он заключается в том, что для выполнения слияний необходим вспомогательный массив, длина которого равна длине сортируемого массива. Поэтому алгоритмы слияния не могут составить конкуренцию для QuickSortиHeapSortв обычных задачах сортировки. Область успешного применения алгоритмов слияния описана в следующем подразделе.

Среди возможных модификаций алгоритма слияния можно упомянуть алгоритм естественного слияния. Его отличие заключается в определении начального набора сливаемых сортированных массивов. Если в алгоритме простого слияния в качестве такого набора использовались отдельные элементы массива, которые мы рассматривали как подмассивы длиной 1, то идея естественного слияния – в том, что исходный несортированный массив с высокой вероятностью уже содержит немало отрезков, на которых элементы расположены по возрастанию. Такие «естественно сортированные» отрезки называютсериями. Легко показать, что в полностью случайном массиве средняя длина серии равна 2. На практике же, как уже отмечалось, могут встречаться частично отсортированные массивы со значительно более длинными сериями. Использование серий в качестве исходного набора сливаемых массивов может привести к уменьшению числа проходов слияния. Однако реализация алгоритма естественного слияния несколько более сложна, чем для простого слияния.