Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей

< <10, 11><8, 9>; <6, 7><4, 5>; <2, 3><1> >, lp=2

< <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4

< <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8

<1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp³ n.

Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.

Даний спосіб сортування можна описати наступною процедурою Mrgsort:

procedure Mrgsort (var A: ArT; n: Indx);

var B: ArT;

lp, npp, cpp, bpp, tl: integer;

begin

lp:= 1;

while lp < n do

begin

B:= A; { копіювання }

npp:= n div (2*lp); { кількість пар ділянок }

tl:= n mod (2*lp); { довжина залишку }

for cpp:= 1 to npp do { cpp – номер пари }

begin

bpp:= (cpp - 1)*2*lp + 1;

{ індекс першого елемента лівої ділянки пари}

mrg (B, bpp, lp, lp, A);

end;

{ обробка залишку }

if tl > lp then

mrg (B, n - tl + 1, lp, tl - lp, A);

{ за tl <= lp залишок був упорядкований }

{ на попередньому кроці }

lp:= lp*2

end;