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

Алгоритмы сортировки слиянием привлекают простотой и наличием важных особенностей: они имеют порядок O(n·log₂n), не имеют худших случаев, допускают сортировку содержимого файлов, размер которых слишком велик для полного размещения в памяти.

Для пояснения алгоритма сортировки поясним сначала принцип слияние. Пусть имеются два отсортированных в порядке возрастания массива p[1], p[2], ..., p[n] и q[1], q[2], ..., q[n] и имеется пустой массив r[1], r[2], ..., r[2n], который требуется заполнить значениями массивов p и q в порядке возрастания.

Для слияния выполняются следующие действия: сравниваются p[1] и q[1], и меньшее из значений записывается в r[1]. Предположим, это значение p[1]. Тогда p[2] сравнивается с q[1] и меньшее из значений заносится в r[2]. Предположим, это значение q[1]. Тогда на следующем шаге сравниваются значения p[2] и q[2] и т.д., пока не будет достигнута граница одного из массивов. Тогда остаток другого массива просто дописывается в конец результирующего массива r.

Такой алгоритм известен как алгоритм двухпутевого слияния. На практике элементы не удаляются из исходных массивов, а используются указатели на текущие начальные элементы, которые при копировании передвигаются на следующий элемент.

Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих массивах. Если в первом находится n элементов, а во втором – m, то в худшем случае потребуется (n+m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n). Пример слияния двух массивов показан на рис. 4.2.

На основеалгоритма двухпутевого слиянияможно прийти к рекурсивному определению сортировки слиянием: исходный массив следует разделить на две половины, применить к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма двухпутевого слияния объединить подсписки в один отсортированный массив. Рекурсивные вызовы завершаются, когда подсписок n-ого уровня, переданный алгоритму сортировки, будет содержать всего один элемент, поскольку он, очевидно, уже отсортирован.

Сортировка слиянием обладает единственным недостатком – требуется наличие третьего списка, в котором будут храниться результаты слияния. Размер требуемой дополнительной памяти составляет до половины размера исходно массива.

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

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

procedure MSS(aList: TList; aFirst, aLast: Integer;

aCompare: TCompareFunc; aTempList: PPointerList);

Var

Mid, i, j, ToInx,

FirstCount: Integer;

Begin

{ Вычислить среднюю точку }

Mid:=(aFirst + aLast) div 2;

{ Рекурсивная сортировка слиянием первой и второй половин списка }

if aFirst < Mid then

MSS(aList, aFirst, Mid, aCompare, aTempList);

if (Mid+1) < aLast then

MSS(aList, Mid+1, aLast, aCompare, aTempList);

{ Скопировать первую половину списка во вспомогательный список }

FirstCount:=Mid-aFirst+1;

Move(aList.List[aFirst], aTempList[0], FirstCount*SizeOf(Pointer));

{ Установить значения индексов: i - индекс для вспомогательного списка

(т.е. первой половины); j - индекс для второй половины списка;