Външно сортиране
Външни методи за сортиране
Обичайно е да се нарича "външно" сортиране на сортирането на последователни файлове, намиращи се във външна памет и твърде големи, за да се преместят изцяло в основната памет и да се приложи един от методите за вътрешно сортиране, разгледани в предишния раздел. Външното сортиране най-често се използва в системите за управление на бази данни при изпълнение на заявки, а производителността на СУБД значително зависи от ефективността на използваните методи.
Трябва също да се отбележи, че действителната скорост на външно сортиране зависи от размера на буфера (или буферите) в основната памет, който може да се използва за тази цел. Ще се съсредоточим върху това в края на тази част от книгата. Първо ще разгледаме основните методи за външно сортиране, работещи с минимален разход на основна памет.
Сливане на сортиране
Сортирането на обединяване обикновено се използва, когато искате да сортирате последователен файл, който не се побира изцяло в основната памет. Съществуват обаче и ефективни вътрешни методи за сортиране, базирани на разделяния и обединения.
Един от популярните вътрешни алгоритми за сортиране на сливания се основава на следните идеи (за улеснение ще приемем, че броят на елементите в масива, както в нашия пример, е степен 2). Първо, нека да обясним какво е сливане. Нека има два масива, сортирани във възходящ ред p [1], p [2],. p [n] и q [1], q [2],. q [n] и има празен масив r [1], r [2],. r [2n], който искаме да запълним със стойностите на масивите p и q във възходящ ред. За обединяване правите следното: p [1] и q [1] се сравняват и по-ниската стойност се записва в r [1]. Да предположим, че това е p [1]. Тогава p [2] се сравнява с q [1] и по-малката от стойностите се въвежда в r [2]. Да предположим, че това е стойността q [1]. След това следващата стъпка сравнява стойностите на p [2] и q [2] и така нататък, докато стигнем до границите на един от масивите. Тогава останалата част от друг масив просто се добавя към "опашката" на масива r.