Естествено сливане
В случай на просто сливане, няма полза от частичното подреждане на сортираните данни. Това е така, защото серията с фиксирана дължина се обединява при всеки проход. При естественото сливане дължината на поредицата не е ограничена, а се определя от броя на елементите във вече подредени подпоследователности, разпределени на всеки проход.
Сорт, който винаги обединява двете най-дълги възможни последователности, е естествено сливане. Това сортиране съчетава сериите с максимална дължина.
Естествен алгоритъм за сортиране на обединяване
Стъпка 1. Оригиналният файл f се разделя на два спомагателни файла f1 и f2. Разпределението е както следва: записите ai на оригиналната последователност (неподредени) се четат един по един по такъв начин, че ако стойностите на ключовете на съседните записи отговарят на условието f (ai) f (ai + 1), след това записите ai + 1 се копират във втория спомагателен файл f2. Процедурата се повтаря, докато всички записи от оригиналната последователност се разпределят между файлове.
Стъпка 2. Спомагателните файлове f1 и f2 се обединяват във файл f, докато серията формира подредени последователности.
Стъпка 3. Полученият файл f се обработва отново, както е посочено в стъпки 1 и 2.
Стъпка 4. Повтаряйки стъпките, обединете подредената серия, докато не бъде подреден целият файл.
Символът "," показва края на поредицата.
Признаците за края на естествения сорт на сливане са следните условия:
- броят на сериите е 1 (определя се във фазата на сливане).
- с еднофазно сортиране вторият спомагателен файл след разпространението на поредицата остана празен.
Естествено сливане, при което след фазата на разпространение броят на сериите в помощните файлове се различава един от друг не повече от един, се нарича балансирано сливане, в противен случай - небалансирано сливане.
По този начин броят на четенията или презаписванията на файлове, използващи метода на естественото сливане, няма да бъде по-лош от използването на метода на простото сливане и средно дори по-добър. Но този метод увеличава броя на сравненията поради тези, необходими за разпознаване на краищата на поредицата. В допълнение, максималният размер на спомагателните файлове може да бъде близък до размера на оригиналния файл, тъй като дължината на поредицата може да бъде произволна.