Sortowanie przez scalanie polega na podzieleniu sortowanej struktury danych na dwie części, następnie na rekurencyjnymrekurencjarekurencyjnym sortowaniu każdej z tych części i ponownym scaleniu już posortowanych części w jedną całość. Warto wiedzieć, że jako pierwszy tę metodę opisał John von NeumannJohn von NeumannJohn von Neumann, znany jako twórca m.in. teorii gier oraz koncepcji automatów komórkowychkoncepcja automatów komórkowychkoncepcji automatów komórkowych. Algorytm sortowania przez scalanie oparty jest na metodzie dziel i zwyciężajdziel i zwyciężajdziel i zwyciężaj.

Scalanie posortowanych tablic

Wyobraźmy sobie, że mamy dwie półki, każda z losową liczbą książek. Książki na półkach ułożone są w kolejności alfabetycznej. Naszym celem jest ułożenie wszystkich książek na trzeciej półce, w kolejności alfabetycznej. By to zrobić, porównujemy ze sobą pierwszą książkę z półki nr 1 z pierwszą książką na półce nr 2. Książka z literą położoną wcześniej w alfabecie, zostaje przeniesiona na trzecią półkę. Czynność powtarzamy, porównując książki, które ułożone są jako pierwsze na półkach. W momencie, gdy skończą nam się książki na jednej z półek, resztę książek z drugiej półki po prostu przenosimy na koniec naszej trzeciej, dodatkowej półki. Aby lepiej zrozumieć algorytm scalania książek na półkach, przeanalizuj rysunek.

R698jHQlBcgzd

Ilustracja przedstawia scalanie posortowanych tablic. Ilustracja podzielona jest na pięć części, w każdej znajdują się trzy tablice.
Część pierwsza, w tablicy 1 znajdują się książki z literami A, E, w 2 z B, K, M, trzecia jest pusta.
W części drugiej w tablicy 1: E, w tablicy 2: B, K, M, w tablicy 3: A.
W części trzeciej w tablicy 1: E, w tablicy 2: K, M, W tablicy trzeciej: A, B.
W części czwartej tablica 1 jest pusta, w tablicy 2: K, M, w tablicy 3: A, B, E.
W części piątej tablica 1 oraz 2 są puste, w tablicy trzeciej znajdują się książki z oznaczeniami: A, B, E, K, M.

Etapy sortowania przez scalanie

Chcemy uporządkować niemalejąco n-elementową tablicę liczb całkowitych. W jaki sposób to zrobić, korzystając z metody sortowania przez scalanie?

Aby użyć omówionego wcześniej algorytmu scalania, musimy podzielić tablicę na mniejsze, same w sobie posortowane tablice. W tym celu tablicę dzielimy na pół – jeżeli liczba elementów jest nieparzysta, pierwsza tablica będzie miała jeden element więcej.

Proces powtarzamy do momentu, w którym osiągniemy tablice jednoelementowe.  Wiemy, że tablica posiadająca jeden element już jest posortowana. Dzięki temu możemy scalić dwie tablice jednoelementowe i uzyskać kolejną, posortowaną dwuelementową tablice. Następnie możemy scalić dwie posortowane tablice dwuelementowe, aby uzyskać czteroelementową itd. Przejdźmy do rysunku przedstawiającego kolejne etapy sortowania przez scalanie na podstawie przykładowej tablicy.

RFhg88Lnkk3gn

Ilustracja przedstawia sortowanie przez scalanie liczby: 85924173. W klamrze opisanej jako podziel znajduje się: liczba pierwotna podzielona na dwie różne części: 8592 oraz 4173.
Następnie znów są dzielone na dwie części: 85, 92 oraz 41, 73.
Następnie pojedyńcze liczby sortowane są rosnąco: 58, 29 oraz 14, 37.
Następnie liczby są scalane: 2589 oraz 1347.
Efektem końcowym jest liczba 123456789.

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”dziel i zwyciężaj„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 podstawowyprzypadek podstawowyprzypadek 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:

Zatem złożoność czasowazłożoność czasowazłożoność czasowa wynosi:

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 miejscusortowanie w miejscusortowaniem w miejscu.

Słownik