Швидкі алгоритми сортування, Детальна інформація

a[i+1]:=x;

i:= i+1;

end

else

begin

if a[j]<=x then

begin

y:=a[j];

a[j]:=a[i+1];

a[i+1]:=y;

end;

j:=j-1

end;

-Qsort (a, low, i-1);

-Qsort (a, i+1, hi);

end;

end;

Процедура Mergesort виконує сортування двох масивів “злиттям”. Тобто, спочатку перший масив сортується за допомогою процедури Qsort і другий масив сортується за допомогою цієї ж процедури. Потім два, вже відсортованих масиви з’єднуються в один. А саме, за допомогою оператору “if” ми порівнюємо перший елемент одного і перший елемент другого масивів. Якщо один з них менший, то ми відсилаємо його в третій масив, а індикатор пересуваємо на наступний елемент і знов порівнюємо їх. Знову менший з двох елементів пересилаємо в третій масив, а індикатор пересуваємо. Також ми передбачили варіант, коли елементи, що порівнюються – однакові. Тоді в третій масив по-черзі записуються обидва елементи, а індикатори зміщуються на наступні елементи в обох масивах. Якщо один з масивів виявився меншим за кількістю елементів ніж інший, то решта елементів довшого масиву просто пересилається до третього масиву в тій самій послідовності (адже вихідні масиви вже відсортовані раніше процедурою Qsort). Таким чином, в результаті ми отримуємо третій масив з впорядкованими елементами.

Procedure Mergesort;

Var i, j, k: byte;

Begin

i:=1;

j:=1;

for k:=1 to n_c do c[k]:=0;

k:=1;

While ( i<= n_a ) or ( j<=n_b ) do

if i= n_a+1 then

begin

c[k]:=b[j];

k:=k+1;