Алгоритмы сортировки слиянием (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. На практике же, как уже отмечалось, могут встречаться частично отсортированные массивы со значительно более длинными сериями. Использование серий в качестве исходного набора сливаемых массивов может привести к уменьшению числа проходов слияния. Однако реализация алгоритма естественного слияния несколько более сложна, чем для простого слияния.