Пряме злиття

Припустимо, що є послідовний файл А, що складається з записів а1,a2,…,an (знову для простоти припустимо, що n є ступенем числа 2). Вважатимемо, що кожен запис складається лише з одного елементу, що є ключем сортування. Для сортування використовуються два допоміжні файли В і С (розмір кожного з них буде n/2).

Сортування складаєтся з послідовності кроків, в кожному з яких виконується розподіл стану файлу А у файли В і С, а потім злиття файлів В і С у файл А. (Помітимо, що процедура злиття для файлів ілюструється рисунком 33). На першому кроці для розподілу послідовно читається файл А, і записи а1, а3, …, а (n-1) пишуться у файл В, а записи а2, а4, …, аn – у файл С (початковий розподіл). Початкове злиття здійснюється над парами (а1,а2), (а3,а4), …, (а(n-1),аn), ш результат записується у файл А. На другому кроці знову послідовно читається файл А, і у файл В записуються послідовні пари з непарними номерами, а у файл С – з парними. При злитті утворюються і пишуться у файл А впорядковані четвірки записів. І так далі. Перед виконанням останнього кроку файл А міститиме дві впорядковані послідовності розміром n/2 кожна. При розподілі перша з них потрапить у файл В, а друга – у файл С. Після злиття файл А міститиме повність впорядковану послідовність записів. У таблиці 10 показаний приклад зовнішнього сортування простим злиттям. Заз начимо, що для виконання зовнішнього сортування методом простого злиття в основній памяті вимагається розташувати всього дві змінні – для розміщення записів з файлів В і С.

Таблиця 10 – Приклад зовнішнього сортування простим злиттям