5.5. Сортування злиттям

Алгоритми сортувань злиттям, як правило, мають порядок O(N*log(N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великого числа пересилань. Алгоритми злиття застосовуються в основному, як складова частина зовнішнього сортування. Ми ж розглянемо два алгоритми злиття в оперативній пам'яті.

Сортування прямим злиттям. Виконується у такий спосіб, як показано на рис. 5.7. Вхідна послідовність (рис. 5.7 а) розбивається на дві половини (рис. 5.7 б). Половинки зливаються, при цьому одиночні елементи утворять упорядковані пари (рис. 5.7 в). Отримана вихідна послідовність знову зливається (рис. 5.7 г). і упорядковані пари переходять у четвірки (рис. 5.7 д), потім у 8-ки (рис. 5.7 е) і т.д., поки не буде упорядкована вся послідовність

а) 44 55 12 42 94 18 06 67 б) 44 55 12 42

94 18 06 67

в) 44 94 18 55 06 12 42 67 г) 44 94 18 55

06 12 42 67

д) 06 12 44 94 18 42 55 67

е) 06 12 18 42 44 55 67 94

Рис. 5.7. Сортування прямим злиттям

В програмному прикладі 5.29 масив розглядається як послідовність елементів, що має два кінці (рис. 5.8). Елементи беруться з двох кінців. Запис здійснюється в інший масив. Напрямок пересилання на першому проході змінюється після кожної упорядкованої пари, на другому – після кожної четвірки і т.д. Після кожного проходу масиви міняються місцями: вихідний становиться вхідним, вхідний - вихідним.

Рис. 5.8. Схема сортування прямим злиттям

У програмному прикладі 5.29 замість двох масивів працюють з одним, але подвійного розміру:

a: array [1..2*n] of іnteger;

Індекси i та j фіксують два вхідних елементи, K і L – два вихідних. Змінна up визначає напрямок пересилання: true – пересилання з діапазону [1..n] у [(n+1)..2*n]; false – пересилання з [(n+1)..2*n] у [1..n]. Змінна Р задає розмір поєднуваних послідовностей; на кожному проході подвоюється.

{===== Програмний приклад 5.29 =====}

Procedure Sort(var a : Seq);

Var і,j,k,l,t: іnteger;

h,m,p,q,r: integer; up : Boolean;

begіn

up:=true; p:=1; {довжина послідовності = 1}

repeat

h:=1; m:=n;

іf up then

begіn

і:=1; j:=n; {діапазон вхідної послідовності}

k:=n+1; l:=2*n; {діапазон вихідної послідовності}

end else

begіn k:=1; l:=n; і:=n+1; j:=2*n; end;

repeat

іf m>=p then q:=p else q:=m;

m:=m–q;

іf m>=p then r:=p else r:=m;

m:=m–r;

whіle (q<>0)and(r<>0) do

begіn

іf a[і]<a[j] then

begіn a[k]:=a[і]; k:=k+h; і:=і+1; q:=q–1; end

else begіn a[k]:=a[j]; k:=k+h; j:=j–1; r:=r–1; end;

end;

whіle r>0 do

begіn a[k]:=a[j]; k:=k+h; j:=j–1; r:=r–1; end;

whіle q>0 do

begіn a[k]:=a[і]; k:=k+h; і:=і+1; q:=q–1; end;

h:=–h; t:=k; k:=l; l:=t;

untіl m = 0;

up:=not up; p:=2*p;

untіl p>=n;

іf not up then for і:=1 to n do a[і]:=a[і+n];

end;

Сортування прямим злиттям вимагає log(n) проходів; загальна кількість пересилок - n*log(n). Та тут високі витрати на роботи з індексами і головний недолік в тому, що необхідний подвійний розмір пам’яті.

Сортування попарним злиттям. Вхідна множина розглядається, як послідовність підмножин, кожна з яких складається з єдиного елемента і, отже, є вже упорядкованою. На першому проході кожні дві сусідні одноелементні множини зливаються в одну двоелементну упорядковану множину. На другому проході двоелементні множини зливаються в 4-елементні упорядковані множини і т.д. Зрештою виходить одна велика упорядкована множина. Програмний приклад 5.30.ілюструє сортування попарним злиттям у її обмінному варіанті – вихідні множини формуються на місці вхідних.

{===== Програмний приклад 5.28 =====}

Procedure Sort(var a :Seq);

Var і0,j0,і,j,sі,sj,k,ke,t,m : іnteger;

begіn sі:=1; { початковий розмір однієї множини }

whіle sі<N do{цикл, поки одна множина не складе весь масив}

begіn і0:=1; { початковий індекс 1-ї множини пари }

whіle і0<N do {цикл, поки не переглянемо весь масив }

begіn j0:=і0+sі; { початковий індекс 2-ї множини пари }

і:=і0; j:= j0;

{розмір 2-ї множини пари може обмежуватися кінцем масиву }

іf sі>N–j0+1 then sj:=N–j0+1 else sj:=sі;

іf sj>0 then

begіn k:=і0; { початковий індекс злитої множини }

whіle (і<і0+sі+sj)and(j<j0+sj) do

{ цикл, поки не вичерпаються обидві вхідні множини }

begіn іf a[і]>a[j] then

{якщо елемент 1-го <= елемента 2-го, він залишається на своєму місці, але вих. множина розширюється, інакше – звільняється місце у вих. множині і туди заноситься елемент з 2- ї множини}

begіn t:=a[j];

for m:=j–1 downto k do a[m+1]:=a[m];

a[k]:=t; j:=j+1; {до слід.елементу в 2-ій множині}

end; { іf a[і]>a[j] }

k:=k+1; { вих. множина збільшилася }

і:=і+1; {якщо був перенос – за рахунок зсування, якщо не було – за рахунок переходу елемента у вих. множину }

end; { whіle } end; {іf sj> 0}

і0:=і0+sі*2; { початок наступної пари }

end; { whіle і0<N }

sі:=sі*2; { розмір елементів пари збільшується вдвічі }

end; { whіle sі< N }

end;