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

В основе алгоритмов сортировки «слиянием» лежит объединение двух упорядоченных последовательностей в одну. Это похоже на перестройку двух колон учеников, выстроенных за ростом, в одну. Ученики, первые в своих колонах, сравниваются; вышей становится в новую колонну, другой остается первым в своей. После этого в колонне, из которой пошел ученик, следующий за ростом учений становится первым. Снова сравниваются первые, и так они действуют, пока в одной из колон никого не останется — тогда сдача другой колонны перейдет в хвост новой без изменения порядка.

Пусть в массиве А з элемента A [L ] начинается упорядоченный участок длиной m-L + 1, а из элемента А [га+1] — участок длиной R-m. Под упорядоченным участком (отрезком или серией) понимаем участок, который не является частью другого упорядоченного участка. Например, длина таких упорядоченных участков равняется m-L + 1 = 3 и R-m = 3.

из
L m m+1 R
Они объединяются в такой участок длиной R-L+1 во вспомогательном массиве В.
13
L m m+1 R
Рассмотрим процедуру слияния в массив Z пары сопредельных участков массива X, в котором левая содержит индексы от L до т, а права — відт+1 flo.
procedure merge(var X,Z:aInt; L,m,R:word); var k:word; {индекс в целевом массиве} и, j:-word; {индексы в половинах) begin
и:=L; j:=т+1; for k: =L to R do
{заполнение элементов Z[L], …, Z[R]) if и>m then
begin Z[k]:=X[j]; inc(j) end else if j>r then
begin Z[k]:=X[i], inc(i) end
Сортировка линейных массивов
else if X[i]<X[j] then
begin Z[k]:=X[i]; inc(i) end else begin Z[k]:=X[j]; inc(j) end end;
Очевидно, тело цикла выполняется R — L + І раз, и каждый раз выполняется 0(1) элементарных действий. Итак, сложность выполнения вызова процедуры merge есть &(R-L + l).

Алгоритм сортировки слиянием заключается в повторении таких шагов слияния пар. В массиве происходит поиск пары сопредельных упорядоченных участков, которые объединяются в один участок вспомогательного массива, например, с помощью процедуры merge. Потом происходит поиск и объединяется следующая пара и т.п.. Возможно, в конце останется участок, который не имеет пары, — ее будет скопировано без перемен. На следующем шаге происходит подобное слияние пар участков вспомогательного массива в основной. Шаги повторяются, пока какой-либо из массивов не превратится на один упорядоченный участок. Если это вспомогательный массив, он копируется в основной. Продемонстрируем выполнение алгоритма на массиве А = < 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> длиной п = 11.

Упорядоченные последовательности выделены дужками < >, пары участков, которые объединяются, отделенные «;», В— имя вспомогательного массива.

А = «11Х10>; <9><8>; <7><6>; <5><4>; <3><2>; <1»
В= «10, 11X8, 9>; <6, 7X4, 5>; <2, 3><1»
Л = «8, 9, 10, 11X4, 5, 6, 7>;<1,2, С»
Я = «4, 5,6, 7, 8, 9, 10, 11X1,2,3»
Л = <1,2, 3, 4, 5,6, 7, 8, 9, 10, 11>

Как видим, массив отсортирован за четыре шага слияния.

После первого шага слияния длина упорядоченных участков не меньше 2 (за исключением, возможно, «хвоста» длиной 1), после второго — не меньше 4 (кроме, возможно, «хвоста» меньшей длины) и т.п.. Итак, после /-го шага длина упорядоченных участков, кроме, возможно, «хвоста», не меньше 2′. Пусть п — количество элементов массива. На последнему, к-му, шаге объединяются две участка; первая из них имеет длину не меньше 24″1, причем 2*»1 < г. Итак, количество шагов к < log« + l. За счет возможного дополнительного копирования количество шагов надо увеличить на 1, но оценка 0(logn) сохранится. На каждом шаге общее количество элементарных действий есть 0(и), поэтому сложность алгоритма — 0(и • log п).

Реализуем алгоритм сортировки слиянием с помощью процедуры sortByMrg. Шаг слияния участков одного массива в другого оформим функцией mergeStep. Она возвращает признак того, что на шаге слияния было найдено хотя бы одну пару упорядоченных участков. Если пара не найдено, то массив, начальный в вызове функции, отсортировано. На непарных шагах слияния функция mergeStep выполняет слияние участков основного массива А у вспомогательный массив В, на парных — наоборот. Якшо массив, начальный в вызове mergeStep, оказался отсортированным на парном шаге слияния, значит, это массив В, и его надо скопировать в основной массив А, А если на непарном шаге, то это массив А, и больше ничего делать не надо.

Пара сопредельных упорядоченных участков и-елементного массива (первый из них начинается индексом left) ищет функция findPair. Она возвращает признак того, что пар найден. Правые границы участков сохраняются в ее параметрах mid и right. Если после ее вызова исполняется условие (lef t=l) and (right=n), то пара не найдено, т.е. массив отсортирован. Для слияния используем процедуру merge (см. выше). Вспомогательная процедура копирования участка массива в другой массив copy Аг есть очевидной.

procedure copyAr<var X,r:alnt;
left,right:word)); var и:word; begin
for i:= left to right do Y[i]:= X[i] end; function findPair(var X:alnt; n,left:word;
var mid, right word): boolean; {функция возвращает признак «того, что пара сопредельных упорядоченные участки найдены} begin
findPair := false; if left <= n then
Сортировка линейных массивов
begin
mid := left;
while (mid<n)and(X[mid]<=X[mid+1]) do
inc(mid); {(mid=n) or (X[mid]>X[mid+l])} if mid~n {правая граница — конец массива} then right:=mid else
begin {поиск правой границы} findPair := true; right := mid+1; while(right<n)and(X[right]<=X [right+1])
do inc(right); {(right=n) or (X[right]>X[right+l]} end; end; end;
function mergeStep(var X,Y:aInt; n.word): boolean;
{функция возвращает признак того, что слияние массива X в массив Y состоялось} var left,mid,right:word; begin
mergestep:=true; left:=l;
while findPair(X,n,left,mid,right) do begin merge(X,Y,left,mid,right) ; left:=right+l end;
{последний вызов findPair возвратил false} if (left=l)and(right=n)
then mergeStep:=false {массив X отсортировано} else if left<=n
then copyAr(X,Y,left,n); {копирование «хвоста»} end;
procedure sortByMrg(var A:alnt; n:word); var B:alnt; {вспомогательный массив}

Алгоритм сортировки слиянием сортирует массивы с большой длиной значительно быстрее, чем базовые методы. Тем не менее его главный недостаток — ему нужный дополнительный массив размером . Алгоритм сортировки слиянием сохраняет взаимное расположение одинаковых значений, т.е. есть стойким. В алгоритмах, основанных на слиянии, элементы последовательности обрабатываются в порядке их расположения, т.е., в сущности, без прямого доступа. Поэтому именно эти алгоритмы используются для внешней сортировки.