If notbUp then

Begin

Begin

Begin

Else

End

Begin

Begin

Repeat

Else

IfbUp then

Repeat

Begin

Var

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

Begin

Begin

Var

Begin

Begin

Begin

Begin

Else

End

Begin

Begin

Begin

Var

Begin

Begin

Else

Begin

Inc(k);

if A[i]<A[j] then

begin A[k]:=A[i]; Inc(i); end

begin A[k]:=A[j]; Inc(j); end;

end;

while i<=q do

// Цикл выполняется, пока левая половина не иссякла

// (правая половина исчерпана)

Inc(k); A[k]:=A[i]; Inc(i);

end;

while j<=r do

// Цикл выполняется, пока правая половина не иссякла

// (левая половина исчерпана)

Inc(k); A[k]:=A[j]; Inc(j);

end;

for i:=1 to n do

// Цикл выполняется для переброски массива из временного места в постоянное

A[i]:=A[i+nCurr];

end;

Ясно, что вызов процедур

СортировкаЛевойПоловины;

СортировкаПравойПоловины;

лучше заменить на рекурсивный вызов самой процедуры, которую мы обсуждаем. Тривиальным случаем следует считать тот, которому соответствует требование отсортировать набор из одного элемента массива.

Ниже приведен полный текст процедуры MergeSort – процедуры сортировки простым слиянием.

procedure MergeSort;

procedure Merge(p, q, r: integer);

i, j, k: integer;

i:=p;

j:=q+1;

k:=n;

while (i<=q) and (j<=r) do

Inc(k);

if A[i]<A[j] then

A[k]:=A[i];

Inc(i);

A[k]:=A[j];

Inc(j);

end;

Inc(nM);

end;

while i<=q do

Inc(k);

A[k]:=A[i];

Inc(i);

end;

while j<=r do

Inc(k);

A[k]:=A[j];

Inc(j);

end;

k:=n;

for i:=p to r do

Inc(k);

A[i]:=A[k];

end;

end;

procedure MergeSortAux(p, r: integer);

q: integer;

if p>=r then exit;

q:=(p+r) div 2;

MergeSortAux(p, q);

MergeSortAux(q+1, r);

Merge(p, q, r);

end;

MergeSortAux(1, nCurr);

end;

Принцип сортировки поясняется следующим примером.

Пусть дан массив

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

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

который состоит из подряд идущих упорядоченных пар.

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

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

который состоит из подряд идущих упорядоченных четверок.

Длина упорядоченных фрагментов растет «в геометрической прогрессии» и за короткое число фаз достигает длины всего массива.

Ниже приведен полный текст процедуры StraightMergeSort – процедуры сортировки прямым слиянием.

procedure StraightMergeSort;

i,j,k,L,t,h,m,p,q,r:

integer;

bUp:

boolean;

nMove:=0;

nCompare:=0;

bUp:=true;

p:=1;

h:=1;

m:=nCurr;

begin i:=1; j:=nCurr; k:=nCurr+1; L:=2*nCurr; end

begin k:=1; L:=nCurr; i:=nCurr+1; j:=2*nCurr; end;

if m>=p then q:=p else q:=m;

m:=m-q;

if m>=p then r:=p else r:=m;

m:=m-r;

while (q<>0) and (r<>0) do

nCompare:=nCompare+1;

if A[i]<A[j] then

A[k]:=A[i];

i:=i+1; q:=q-1;

A[k]:=A[j];

j:=j-1; r:=r-1;

end;

nMove:=nMove+2;

k:=k+h;

end;

while r>0 do

A[k]:=A[j];

nMove:=nMove+2;

k:=k+h; j:=j-1; r:=r-1;

end;

while q>0 do

A[k]:=A[i];

nMove:=nMove+2;

k:=k+h; i:=i+1; q:=q-1;

end;

h:=-h; t:=k; k:=L; L:=t;

until m=0;

bUp:= not bUp;

p:=2*p;

until p>=nCurr;

for i:=1 to nCurr do

Дата добавления: 2014-01-04