Сортування злиттям: алгоритм, переваги і особливості

Реалізація алгоритму

Сортування злиттям в Паскалі показана нижче.

Procedure MergeSort(name: string; var f: text);
Var a1,a2,s,i,j,kol,tmp: integer;
f1,f2: text;
b: boolean;
Begin
kol:=0;
Assign(f,name);
Reset(f);
While not EOF(f) do
begin
read(f,a1);
inc(kol);
End;
Close(f);
Assign(f1,'{ім’я 1-го допоміжного файлу}’);
Assign(f2,'{ім’я 2-го допоміжного файлу}’);
s:=1;
While (sВізуально робота алгоритму виглядає так (зверху – невпорядкована послідовність, знизу – упорядкована.

Зовнішня сортування даних

Дуже часто з’являється необхідність упорядкувати деякі дані, розташовані в зовнішній пам’яті ЕОМ. У ряді випадків вони мають значні розміри і не можуть бути розміщені в оперативній пам’яті для полегшення доступу до них. Для таких випадків використовуються методи зовнішніх сортувань.

Необхідність звертатися до зовнішніх носіїв погіршує тимчасову ефективність обробки.

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

Читання даних з зовнішнього джерела, їх обробка та запис в кінцевий файл здійснюються впорядкованими блоками (серіями). За способом роботи з розміром впорядкованих серій виділяють два види сортування: просте і природне злиття.