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

Анимация на сортиране чрез сливане. Елементите са представени като точки

В информатиката сортирането чрез сливане е алгоритъм за сортиране, базиран на сравняване, който винаги има сложност $\Theta (nlog(n))$. Алгоритъмът се гради на принципа „разделяй и владей“. Създаден е от Джон фон Нойман през 1945. Стабилен е и паметта, която му трябва, в най-лошия случай е n. По-подробно описание и анализ на сортирането чрез сливане, се е появило в доклад на Goldstine и Neumann още през 1948 година.

Принцип на действие

1. Несортираният списък по произволен начин се разделя на два подсписъка с приблизително еднаква дължина (за линейно време)
2. Рекурсивно се разделят подсписъците, докато не се достигне до списъци с единична дължина
3. Сливат се два подсписъка в нов сортиран списък (за линейно време)

Примерен код на C#

Има 2 метода. Първият разделя масива на 2, а втория сравнява елементите.

static int[] Splits(int[] arr)
{
 if (arr.Length == 1) // Ако дължината на масива стане равна на 1 елемент,
 { // тогава се връща този елемент и отиваме към другия метод
 return arr;
 }
 // Инициализират се два масива с равен брой елемента спрямо подаденият масив(arr).
 int middle = arr.Length / 2;
 int[] leftArr = new int[middle];
 int[] rightArr = new int[arr.Length - middle];
 // Слагаме в първия масив(left), половината от елементите на подадения масив (arr).
 for (int i = 0; i < middle; i++)
 {
 leftArr[i] = arr[i];
 }
 // Слагаме във втория масив(right), другата половината от елементи на подадения масив (arr).
 for (int i = middle, j = 0; i < arr.Length; i++, j++)
 {
 rightArr[j] = arr[i];
 }

 leftArr = Splits(leftArr); // Вика се рекурсия на лявата половина, докато нейната дължина не стане равна на 1.
 rightArr = Splits(rightArr); // След като свършим изцяло с лявата половина на първоначално подадения масив,
 // прави се същото и с дясната половина, докато не се изчерпят всички нейни стойности

 return Merge(leftArr, rightArr); // Когато в двата масива остане само по 1 елемент, викаме метода
 // Merge, който ще ги слее, разпределени по големина

}

Във втория метод ще трябват променливите leftIncrease и rightIncrease, за да се ходи по елементите на масивите.

static int[] Merge(int[] left, int[] right)
{
 // Първоначално се сравнява нулевия елемент на левия масив с нулевия елемент на десния.
 int leftIncrease = 0;
 int rightIncrease = 0;
 int[] arr = new int[left.Length + right.Length];
 for (int i = 0; i < arr.Length; i++)
 {
 // Ако левият елемент е по-малък, той се записва в масива (arr) и се увеличава левия брояч (leftIncrease) с 1
	// Ако всички елементи в десния масив свършат, то се прехвърлят автоматично останалите елементи в левия масив.
 if (rightIncrease == right.Length || ((leftIncrease < left.Length) && (left[leftIncrease] <= right[rightIncrease])))
 {
 arr[i] = left[leftIncrease];
 leftIncrease++;
 }
 else if (leftIncrease== left.Length || ((rightIncrease < right.Length)&&(left[leftIncrease] >= right[rightIncrease])))
 {
 arr[i] = right[rightIncrease];
 rightIncrease++;
 }
 }
 return arr;
}

Пример стъпка по стъпка

Пример, как сортирането чрез сливане сортира една редица.

Предимства и недостатъци

Предимството на сортирането чрез сливане е, че винаги работи със сложност $nlog(n)$. Това е теоретически най-добрата алгоритмична сложност, която може да бъде постигната от универсален алгоритъм за сортиране. Недостатъкът му е, че допълнителната памет, която му трябва, е n. Тоест, ако имаме 1 милион елемента, то ще ни трябва памет за 2 милиона елемента, за да изпълним алгоритъма.

Паралелна обработка

Алгоритъмът може да се използва паралелно, тоест на всяко едно ядро на процесора му се подава методът, който разделя масива на 2, и после се сливат числата наведнъж. Ако имаме 8 микропроцесора, на всеки процесор му се дава методът Split, и след това се съединяват наведнъж всичките 8 части. Алгоритъмът може да стане n пъти по-бърз, когато имаме n ядра.