Природне злиття

При використанні методу прямого злиття не береться до уваги те, що початковий файл може бути частково відсортованим, тобто містити впорядковані підпослідовності записів.

Серією називається підпослідовність записів аі, а(i+1),..., aj така, що ak<=a(k+1) для всіх i<= k<j, аі < а(і-1) і aj>a(j+1). Метод природного злиття ґрунтується на розпізнаванні серій при розподілі і їх використанні при подальшому злитті.

Як і у разі прямого злиття, сортування виконується за декілька кроків, в кожному з яких спочатку виконується розподіл файла А по файлам В і С, а потім злиття В і С у файл А. При розподілі розпізнається перша серія записів і переписується у файл В, друга - у файл С і т.ін. При злитті перша серія записів файлу В зливається з першою серією файлу С, друга серія В з другою серією С і т.ін. Якщо перегляд одного файлу закінчується раніше, ніж перегляд іншого (внаслідок різної кількості серій), то залишок не до кінця переглянутого файла повністю копіюється в кінець файла А. Процес завершується, коли у файлі А залишається тільки одна серія. Приклад сортування файла показаний на рисунках 34 і 35.

Рисунок 34 – Зовнішнє пряме сортування злиттям. Перший крок.

Рисунок 35 – Зовнішнє пряме сортування злиттям. Другий крок.

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