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