Сливане на сортиране

Алгоритмите за сортиране на масиви не винаги са приложими, ако сортираните данни се намират в структура с последователен достъп, която се характеризира с факта, че във всеки момент има директен достъп до един и само един компонент.

Основният метод, използван за сортиране на файлове, е сортиране чрез сливане .
Merge sort е алгоритъм за сортиране, който подрежда списъци (или други структури от данни, чиито елементи могат да бъдат достъпни само последователно, например потоци) в определен ред.

Обединяването означава комбиниране на две (или повече) последователности в една подредена последователност чрез циклично избиране на наличните в момента елементи.

Първо, задачата е разделена на няколко по-малки подзадачи. След това тези задачи се решават с помощта на рекурсивно повикване или директно, ако размерът им е достатъчно малък. След това техните решения се комбинират и се получава решение на първоначалния проблем.

Операция, която обработва много данни веднъж, се нарича фаза .

Най-малкият подпроцес, който се повтаря, за да образува процес на сортиране, се нарича пропуск или стъпка .

Процедурата на сливане включва обединяване на две предварително подредени подпоследователности на измерение n/2 в една последователност от измерения н. Първоначалните елементи на предварително поръчаните последователности се сравняват помежду си и се избира най-малкият. Съответният указател се придвижва към следващия елемент. Процедурата се повтаря, докато се достигне края на една от последователностите. Останалите елементи от друга подпоследователност се прехвърлят в получената последователност непроменени.

Сливането на обединяването много прилича на метода на бързото сортиране. Ефективността на сортиране на сливане се намира между производителността на купчина и бърза сортировка. Но за разлика от сортирането на купчина и бързи сортировки, сортирането на обединяване е стабилно, защото не зависи от пермутации на елементи в масива.

Друго предимство на сортирането на обединяване е, че е полезно за структури с последователен достъп до елементи, като файлове на външно устройство или свързани списъци. Този метод се използва предимно за външно сортиране.

Недостатъците на този метод са, че той изисква допълнителна памет, равна на размера на файла за сортиране. Следователно за големи файлове е проблематично да се организира сортиране на обединяване в RAM.

В случаите, когато гарантираното време за сортиране е важно и разположението в паметта, методът за сортиране на обединяване може да бъде предпочитан.

Двупосочен алгоритъм за сливане

Оригиналната последователност е разделена на две подпоследователности:

Тези две подпоследователности се комбинират в една, съдържаща подредени двойки.

Получената последователност отново се разделя на две и двойките се комбинират в подредени четворки:

Получената последователност отново се разделя на две и се сглобява в подредени осмици.

Тази операция се повтаря, докато получената подредена последователност има същия размер като тази, която се сортира.

Основната операция е сливане. Обединяването изисква допълнителна памет, за да побере обединения файл. Работата линейно зависи от броя на елементите в комбинираните масиви.

C реализация на двупосочния метод на сливане