Pseudokod sortowania przez scalanie

Specyfikacja:

Dane:

• n – liczba naturalna dodatnia, liczba elementów tablicy

• tablica – n‑elementowa tablica liczb całkowitych

Wynik:

• posortowana niemalejąco tablica całkowitych liczb tablica

Algorytm ten można zapisać za pomocą pseudokodu w następujący sposób:

funkcja Sortowanie_scalanie(tablica, pocz, kon)
	jeżeli pocz < kon
		połowa ← zaokrąglij w dół do całkowitej((pocz + kon) / 2)
		Sortowanie_scalanie(tablica, pocz, połowa)
		Sortowanie_scalanie(tablica, połowa + 1, kon)
		Scal(tablica, pocz, połowa, kon)
        
funkcja Scal(tablica, pocz, polowa, kon)
    n1 ← polowa - pocz + 1
    n2 ← kon - polowa

    utwórz tablicę L o rozmiarze n1
    utwórz tablicę R o rozmiarze n2

    dla i od 0 do n1 - 1
        L[i] ← tablica[pocz + i]

    dla j od 0 do n2-1
        R[j] ← tablica[polowa + 1 + j]

    i ← 0
    j ← 0
    k ← pocz

    dopóki i < n1 ORAZ j < n2
        jeżeli L[i] <= R[j]
            tablica[k] ← L[i]
            i ← i + 1
        w przeciwnym razie
            tablica[k] ← R[j]
            j ← j + 1
        k ← k + 1

    dopóki i < n1
        tablica[k] ← L[i]
        i ← i + 1
        k ← k + 1

    dopóki j < n2
        tablica[k] ← R[j]
        j ← j + 1
        k ← k + 1

W jaki sposób zastosowane jest podejście „dziel i zwyciężaj” w zapisanym pseudokodzie?

Przeanalizujmy wspólnie instrukcję tego algorytmu. Na początek sprawdzamy, czy podana tablica zawiera więcej niż jeden element. Jeżeli odpowiedź brzmi tak, przechodzimy do kolejnych poleceń.

Od tego kroku zostaje wykorzystana strategia „dziel i zwyciężaj”.  Przyjrzyj się i spróbuj zauważyć podobieństwo opisu tej strategii z zapisanym wcześniej za pomocą pseudokodu algorytmem sortowania.

• Do zmiennej połowa zapisywany jest indeks podziału tablicy. Pamiętajmy, żeby wynik zaokrąglić w dół do części całkowitej. Dzięki temu tablica będzie podzielona na dwie części. W przypadku parzystej liczby elementów, będą to dwie równe części, w wypadku nieparzystej – pierwsza część będzie zawierała o jeden element więcej od drugiej.

• Następnie rekurencyjnie wywołujemy funkcję sortowania przez scalanie, osobno dla każdej z dwóch części. Tablica dzielona jest aż do otrzymania tablic jednoelementowych, czyli aż do momentu, w którym algorytm znajdzie przypadek podstawowy.

• Ostatnia instrukcja pseudokodu wywołuje funkcję, która łączy posortowane fragmenty tablic w jedną posortowaną tablicę.

Złożoność czasowa i pamięciowa algorytmu

Tablica dzielona jest zawsze na dwie części (co mogliśmy zaobserwować na rysunku przedstawiającym kolejne etapy sortowania przez scalanie tablicy liczb). W wypadku parzystej liczby elementów są to zawsze dwie równe części. W przypadku nieparzystej liczby elementów pierwsza część zawiera tylko o jeden element więcej od drugiej. Zatem dla n‑elementowej tablicy, mamy ${\log }_2\left(n\right)$ poziomów zagnieżdżenia funkcji. Złożoność operacji scalania na każdym poziomie drzewa niezależnie od uporządkowania elementów wynosi $n\cdot c$, gdzie c jest stałą zależną od jakości używanego sprzętu. A więc czas działania algorytmu zarówno dla zbiorów posortowanych, posortowanych odwrotnie jak i nieposortowanych jest proporcjonalny do:

$n·{log}_{2}n$

Zatem złożoność czasowa wynosi:

$O(n·{log}_{2}n)$

Sortowanie przez scalanie wymaga użycia dodatkowej tablicy, w której będziemy zachowywać wynik scalania, więc dla n‑elementowej tablicy złożoność pamięciowa wynosi O(n). W związku z tym, merge sort nie jest tzw. sortowaniem w miejscu.