Sortowanie przez scalanie (merge sort)

Ponieważ używamy algorytmu dziel-i-rządź do sortowania, musimy zdecydować jak będą wyglądać nasze podproblemy. Pierwotny problem to posortowanie całej tablicy. Powiedzmy, że podproblemem jest posortowanie podtablicy. W szczególności myślimy o podproblemie posortowania podtablicy rozpoczynającej się indeksem $p$p i kończącej się indeksem $r$r. To będzie ważne, abyśmy znali oznaczenie dla podtablicy, więc powiedzmy, że array[p..r] oznacza podtablicę array. Zauważ, że ta notacja z "dwiema kropkami" nie jest poprawna dla JavaScript; używamy jej tu tylko po to, aby opisać działanie algorytmu, a nie po to by podać sposób jego implementacji w kodzie. Biorąc pod uwagę nasze oznaczenia, dla tablicy $n$n-elementowej, nasz pierwotny problem to posortowanie tablicy array[0..n-1].

Oto jak sortowanie przez scalanie używa algorytmu dziel-i-rządź:

Potrzebujemy przypadku bazowego. Przypadkiem bazowym jest podtablica zawierająca mniej niż dwa elementy, co ma miejsce, gdy $p \geq r$p, is greater than or equal to, r, wtedy podtablica nie ma już żadnych elementów lub posiada jeden element, który jest już posortowany. Czyli wykonujemy algorytm dziel-i-rządź tylko wtedy, gdy $p < r$p, is less than, r.

Spójrzmy na przykład. Zacznijmy od tablicy zawierającej [14, 7, 3, 12, 9, 11, 6, 2]. Pierwsza podtablica jest tak naprawdę pełną tablicą array[0.{,}7] ($p=0$p, equals, 0 i $r=7$r, equals, 7). Ta podtablica posiada przynajmniej dwa elementy, więc nie jest przypadkiem bazowym.

A jak podtablica array[0..3] została posortowana? W ten sam sposób. Posiada ona więcej niż dwa elementy, więc nie jest przypadkiem bazowym. Dla $p=0$p, equals, 0 i $r=3$r, equals, 3, obliczamy $q=1$q, equals, 1, rekurencyjnie sortujemy array[0..1] ([14, 7]) oraz array[2..3] ([3, 12]), w rezultacie czego podtablica array[0..3] zawierająca [7, 14, 3, 12], po scaleniu pierwszej podtablicy z drugą podtablicą, wygląda tak: [3, 7, 12, 14].

A jak podtablica array[0..1] została posortowana? Dla $p=0$p, equals, 0 i $r=1$r, equals, 1, obliczamy $q=0$q, equals, 0, rekurencyjnie sortujemy array[0..0] ([14]) oraz array[1..1] ([7]), w rezultacie czego podtablica array[0..1] zawierająca [14, 7], po scaleniu pierwszej podtablicy z drugą podtablicą, wygląda tak: [7, 14].

Podtablice array[0..0] oraz array[1..1] są przypadkami bazowymi, ponieważ każda z nich zawiera mniej niż dwa elementy. Poniżej przedstawiony jest cały algorytm sortowania przez scalanie:

Większość kroków w sortowaniu przez scalanie jest prosta. Można łatwo sprawdzić przypadek bazowy. Odnalezienie punktu środkowego $q$q w kroku dzielenia również jest bardzo łatwe. Musimy jedynie zrobić dwa odwołania rekurencyjne w kroku "rządź". Tak naprawdę najtrudniejszy jest krok połączenia dwóch posortowanych podtablic.

Nasze kolejne wyzwanie będzie polegać na zaimplementowaniu kompletnego algorytmu sortowania przez scalanie, aby upewnić się że rozumiesz jak rekurencyjnie korzystać z algorytmu "dziel i rządź". Następnie zajmiemy się szczegółowo efektywnym scalaniem dwóch posortowanych macierzy w jedną macierz - algorytm, który implementujesz w późniejszym wyzwaniu.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.