Преглед на сортиране чрез сливане

Тъй като използваме "разделяй и владей" за сортиране, трябва да решим как ще изглеждат нашите подзадачи. Цялата задача е да сортираме целия масив. Да речем, че подзадачата ни е да сортираме подмасив. По-конкретно, ще определим една подзадача като сортиране на подмасива, като започнем от индекс $p$‍ и продължим до индекс $r$‍. Ще бъде удобно да имаме означение за подмасива, затова нека приемем, че array[p..r] обозначава този подмасив на array. Забележи, че това отбелязване с "две точки" не е легален JavaScript; използваме го само за да опишем алгоритъма, а не конкретна имплементация на алгоритъма в кода. По отношение на нашата нотация за масив от $n$‍ елемента можем да кажем, че оригиналната задача е да сортираме array[0..n-1].

Ето как сортирането чрез сливане използва принципа "разделяй и владей":

Трябва ни основен случай. Основният случай е подмасив, който има по-малко от два елемента, което е изпълнено, когато $p\ge r$‍, тъй като един подмасив без елементи или само с един елемент вече е сортиран. Затова изпълняваме "разделяй-владей-комбинирай", само когато $p<r$‍.

Да видим един пример. Да започнем с array, който съдържа [14, 7, 3, 12, 9, 11, 6, 2], тогава първият подмасив всъщност е целия масив, array[0..7] ($p=0$‍ и $r=7$‍). Този подмасив има поне два елемента и не е основен случай.

Как така масивът array[0..3] е сортиран? По същия начин. В него има повече от два елемента, затова не е основен случай. С $p=0$‍ и $r=3$‍, изчисляваме $q=1$‍, сортираме рекурентно array[0..1] ([14, 7]) и array[2..3] ([3, 12]), което дава array[0..3], който съдържа [7, 14, 3, 12] и сливаме първата половина с втората половина, което ни дава [3, 7, 12, 14].

Как така масивът array[0..1] е сортиран? С $p=0$‍ и $r=1$‍, изчисляваме $q=0$‍, сортираме рекурентно array[0..0] ([14]) и array[1..1] ([7]), което дава array[0..1], който все още съдържа [14, 7] и сливаме първата и втората половина, за да получим [7, 14].

Подмасивите array[0..0] и array[1..1] са основни случаи, тъй като всеки от тях съдържа по-малко от два елемента. Ето как се случва целият алгоритъм на сортиране:

Повечето от стъпките в сортирането чрез сливане са прости. Можеш лесно да провериш за основния случай. Намирането на средната точка $q$‍ в стъпката "разделяне" също е лесно. Трябва да направиш две рекурентни повиквания в стъпката "завладяване". Това е комбиниращата стъпка, в която трябва да слееш двата сортирани подмасива, където се случва същинската работа.

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

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.