Пошук, сортування та поняття складності, Детальна інформація

Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,

Y … 1 3 … 13 2 4 … 88

  … m m+1   m+s-1 m+s m+s+1 … m+s+r

Результатом злиття повинна бути ділянка довжини r+s у масиві X:

X … 1 2 3 4 … 13 … 88

  … m m+1 m+2 m+3   …   m+s+r

За дії означень (17.1) таке злиття двох ділянок у масиві Y у ділянку масиву X задає процедура

procedure mrg( var Y : ArT; m, s, r : Indx; var X : ArT);

var mr, k : Indx; i, j : Extind;

begin

mr := m + s; { mr – початок правої частини }

i := m; j := mr; { i та j пробігають ліву й праву ділянки масиву Y}

for k := m to m + s + r - 1 do{заповнення X[m], … , X[m+s+r-1]}

if i > m + s - 1 then

begin X[k] := Y[j]; j := j + 1 end else

if j > mr + r - 1 then

begin X[k] := Y[i]; i := i + 1 end else

if Y[i] < Y[j] then

begin X[k] := Y[i]; i := i + 1 end else

begin X[k] := Y[j]; j := j + 1 end

end

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], … , A[n] копіюються в допоміжний масив B[1], … , B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.

На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.

Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.

Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";":

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

< <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