Sortowanie przez scalanie

Sortowanie przez scalanie w wersji rekurencyjnej

W informatyce sortowanie przez scalanie (ang. merge sort), to rekurencyjny algorytm sortowania danych, stosujący metodę dziel i zwyciężaj. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi^{[potrzebne źródło]}.

Algorytm

Wyróżnić można trzy podstawowe kroki:

1. Podziel zestaw danych na dwie równe części
2. Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element;
3. Połącz posortowane podciągi w jeden.

W pseudokodzie algorytm można zapisać następująco:

SORT-SCAL(T, p, r):
    JEŚLI p < r:
        q → (p+r)/2
        SORT-SCAL(T, p, q)
        SORT-SCAL(T, q+1, r)
        SCALANIE(T, p, q, r)

Procedura scalania dwóch ciągów A[1..n] i B[1..m] do ciągu C[1..m+n]^{[potrzebne źródło]}:

1. Utwórz wskaźniki na początki ciągów A i B → i=1, j=1
2. Jeżeli ciąg A wyczerpany (i>n), dołącz pozostałe elementy ciągu B do C i zakończ pracę.
3. Jeżeli ciąg B wyczerpany (j>m), dołącz pozostałe elementy ciągu A do C i zakończ pracę.
4. Jeżeli A[i] ≤ B[j] dołącz A[i] do C i zwiększ i o jeden, w przeciwnym przypadku dołącz B[j] do C i zwiększ j o jeden
5. Powtarzaj od kroku 2 aż wszystkie wyrazy A i B trafią do C

Scalenie wymaga O(n+m) operacji porównań elementów i wstawienia ich do tablicy wynikowej.

Zobacz przykłady implementacji tego algorytmu na stronie Wikiźródeł

Zastosowanie

Szczególnie jest przydatny zwłaszcza przy danych dostępnych sekwencyjnie (po kolei, jeden element na raz), na przykład w postaci listy jednokierunkowej (tj. łączonej jednostronnie) albo pliku sekwencyjnego^{[potrzebne źródło]}.

Złożoność czasowa

Sortowanie przez scalanie zastosowane do tablicy 7-elementowej.

Obrazek obok przedstawia drzewo rekursji wywołania algorytmu mergesort.

Mamy więc drzewo o głębokości log₂ n, na każdym poziomie dokonujemy scalenia o łącznym koszcie n×c, gdzie c jest stałą zależną od komputera. A więc intuicyjnie, tzn. nieformalnie możemy dowieść, że złożoność algorytmu mergesort to log₂ n×n

Formalnie złożoność czasową sortowania przez scalanie możemy przedstawić następująco:

Bez straty ogólności załóżmy, że długość ciągu, który mamy posortować jest potęgą liczby 2.

$T(1) = O(1)$

$T(n) = 2T(\tfrac{n}{2}) + O(n)$

Ciągi jednoelementowe możemy posortować w czasie stałym, czas sortowania ciągu n–elementowego to scalenie dwóch ciągów $\tfrac{n}{2}$–elementowych, czyli O(n), plus czas potrzebny na posortowanie dwóch o połowę krótszych ciągów.

Mamy:

$\begin{array}{cl} T(n) & = 2T(\tfrac{n}{2}) + n = 2(2T(\tfrac{n}{4}) + \tfrac{n}{2}) + n \\ \\ & = 2(2(2T(\tfrac{n}{8}) + \tfrac{n}{4}) + \tfrac{n}{2}) + n \\ \\ & = 2(2(...2(T(\tfrac{n}{2\cdot 2^i})+\tfrac{n}{2^i})++...)+\tfrac{n}{2})+n \\ \\ & = 2(2(...2(T(1)+2)...)+\tfrac{n}{2})+n \end{array}$

gdzie $n=2^k$

Po rozwinięciu nawiasów otrzymamy: $T(n) = 2n\log n$ A więc asymptotyczny czas sortowania przez scalanie wynosi O(n log n) (zobacz: notacja dużego O).

Wersja nierekurencyjna

Podstawową wersję algorytmu sortowania przez scalanie można uprościć. Pomysł polega na odwróceniu procesu scalania serii. Ciąg danych możemy wstępnie podzielić na n serii długości 1, scalić je tak, by otrzymać $\tfrac{n}{2}$ serii długości 2, scalić je otrzymując $\tfrac{n}{4}$, serii długości 4...

Złożoność obliczeniowa jest taka sama jak w przypadku klasycznym, tu jednak nie korzystamy z rekursji, a więc zaoszczędzamy czas i pamięć potrzebną na jej obsłużenie.

Linki zewnętrzne

• Przyśpieszony MergeSort
• Algorytm przedstawiony z wykorzystaniem tańca