Сортиране чрез просто сливане
Да предположим, че имаме последователен файл A, състоящ се от записи a1, a2, . ан. За сортиране се използват два помощни файла B и C.
Сортирането се състои от поредица от стъпки, всяка от които разпределя състоянието на файл A във файлове B и C и след това обединява файлове B и C във файл A. В първата стъпка файл A се чете последователно за разпространение и записва a1, a3. се записват във файл B, а записите a2, a4. -към файл C. Първоначалното сливане се извършва върху двойките (a1, a2), (a3, a4). и резултатът се записва във файл A. Във втората стъпка файл A отново се чете последователно и последователните двойки с нечетни номера се записват във файл B, а двойките с четни номера се записват във файл C. При сливането се формират подредени четворки от записи и се записват във файл A. И така нататък. Преди последната стъпка файл A ще съдържа две подредени подпоследователности. При разпространение първият от тях ще попадне във файл B, а вторият - във файл C. След сливането файл A ще съдържа напълно подредена последователност от записи.
За да се извърши външно сортиране чрез директно сливане, само две променливи трябва да бъдат разпределени в основната памет - за да се поберат следващите записи от файлове B и C.
Общото количество работа, извършено от алгоритъма, е по същество пропорционално наm + n,така че е ясно, че сливането е по-лесна задача от сортирането. Задачата за сортиране обаче може да бъде намалена до сливане, сливане на все по-дълги подфайлове, докато целият файл бъде сортиран. Този подход може да се разглежда като развитие на идеята за сортиране чрез вмъкване: вмъкването на нов елемент в подреден файл е специален случай на сливане, когатоn =1!
Естествено сортиране чрез сливане
При използване на метода на директно сливане не се взема предвидМоля, обърнете внимание, че изходният файл може да е частично сортиран, т.е. съдържат подредени подпоследователности от записи. Серията е подпоследователност от записи ai, a(i+1), . aj, така че ak a(j+1). Методът на естественото сливане се основава на разпознаването на серии по време на разпространението и използването им при последващо сливане.