2. Сортиране чрез сливане
Процедурата на сливане изисква два сортирани масива. Отбелязвайки, че масив от един елемент по дефиниция е сортиран, можем да го сортираме по следния начин:
разделяне на наличните елементи на масива на двойки и обединяване на елементите от всяка двойка, получаване на сортирани вериги с дължина 2 (освен, може би, един елемент, за който не е намерена двойка);
разделяне на съществуващите сортирани вериги на двойки и обединяване на веригите на всяка двойка;
ако броят на сортираните низове е по-голям от един, преминете към стъпка 2.
Най-лесно е този алгоритъм да се формализира по рекурсивен начин (в следващия раздел ще приложим този алгоритъм по итеративен начин). Функцията сортира секцията на масива от елемент с номер a до елемент с номер b:
Тъй като функцията сортира само част от масива, когато обединява два фрагмента, тя няма друг избор освен да разпредели временен буфер за резултата от обединяването и след това да копира данните обратно:
void MergeSort(char* M, int c)
if(c+M[n\2]+ N, където M1=0. Тази рекурсивна връзка също описва сумата от етикетите на възлите и дължината на външния път). Това твърдение е лесно за проверка, когатоNе степен на 2, докажете чрез индукция за произволноN.
Сортирането чрез сливане използва допълнително пространство, пропорционално на N.
Можем да предприемем някои стъпки, за да намалим количеството използвано допълнително пространство, като направим алгоритъма много по-сложен.Сортирането чрез сливане също е ефективно, ако файлът, който се сортира, е организиран като свързан списък. В този случай посоченото свойство се запазва, но се заема допълнително място в паметта за връзките. В случай на масиви,както е отбелязано в раздела, възможно е да се извърши обменно сливане, но тази стратегия е малко вероятно да бъде оправдана на практика.
Сортирането чрез сливане е стабилно, ако използваният метод на сливане е стабилен.
Това твърдение лесно се проверява чрез индукция. За да се приложи методът на сливане, предложен в програма 8.1, е лесно да се покаже, че относителната позиция на дублираните ключове не е нарушена. Въпреки това, колкото по-сложен е алгоритъмът, толкова по-голяма е вероятността тази стабилност да бъде нарушена.
Изискването за ресурс от страна на сортирането чрез сливане не е чувствително към оригиналния ред на входния файл.
В нашите реализации входът определя само реда, в който елементите се обработват по време на сливания. Всяко преминаване изисква място в паметта и брой стъпки, пропорционални на размера на подфайла. което се дължи на необходимостта от разходите за преместване на данни към спомагателен файл. Съответните два клона на израза if може да изискват малко по-различно време за завършване на компилацията, което от своя страна води до известна зависимост на времето за изпълнение от естеството на входните данни, но броят на сравненията и другите операции не зависи от това как е подреден входният файл.