Sortowanie przez scalanie (mergesort)

WPROWADZENIE

Algorytm sortowania przez scalanie wymaga dodatkowego obszaru pamięci proporcjonalnego do liczby n sortowanych elementów. Sortowanie przez scalanie jest stabilne. Metoda dobrze nadaje się do sortowania danych dostępnych sekwencyjnie (listy). Czas działania algorytmu nie zależy od sposobu uporządkowania danych wejściowych.

• Dziel (Divide): Podziel n-elementową sekwencję do posortowania na dwie sekwencje o długości n/2 każda.
• Zwyciężaj (Conquer): Posortuj dwie podsekwencje rekurencyjnie wykorzystując mergesort.
• Połącz (Combine): Złącz dwie posortowane sekwencje w jedną posortowaną sekwencję, która stanowi rozwiązanie.

def mergesort(L, left, right):
    """Sortowanie przez scalanie."""
    if left < right:
        middle = (left + right) // 2   # wyznaczanie środka 
        mergesort(L, left, middle)
        mergesort(L, middle + 1, right)
        merge(L, left, middle, right)   # scalanie

def merge(L, left, middle, right):
    """Łączenie posortowanych sekwencji."""
    T = [None] * (right - left + 1)
    left1 = left
    right1 = middle
    left2 = middle + 1
    right2 = right
    i = 0
    while left1 <= right1 and left2 <= right2:
        if L[left1] <= L[left2]:   # mniejsze lub równe
            T[i] = L[left1]
            left1 += 1
        else:
            T[i] = L[left2]
            left2 += 1
        i += 1
    # Lewa lub prawa część może mieć elementy.
    while left1 <= right1:
        T[i] = L[left1]
        left1 += 1
        i += 1
    while left2 <= right2:
        T[i] = L[left2]
        left2 += 1
        i += 1
    # Skopiuj z tablicy tymczasowej do oryginalnej.
    for i in range(right - left +1):
        L[left + i] = T[i]

def merge(L, left, middle, right):
    """Łączenie posortowanych sekwencji z wartownikami."""
    n1 = middle - left + 1
    n2 = right - middle
    A = [None] * (n1 + 1)   # o jeden więcej
    B = [None] * (n2 + 1)   # o jeden więcej
    for i in range(n1):
        A[i] = L[left + i]
    for i in range(n2):
        B[i] = L[middle + 1 + i]
    A[n1] = float("inf")   # wartownik
    B[n2] = float("inf")   # wartownik
    i, j = 0, 0
    for k in range(left, right+1):
        if A[i] <= B[j]:
            L[k] = A[i]
            i += 1
        else:
            L[k] = B[j]
            j += 1

ZŁOŻONOŚĆ

Czas sortowania listy o długości n oznaczamy przez T(n), przy czym T(1) = c. Z definicji algorytmu dostajemy zależność rekurencyjną
T(n) = 2 * T(n/2) + c * n,
gdzie c * n to czas scalenia dwóch uporządkowanych ciągów w jeden ciąg n elementowy.

Z twierdzenia wynika, że czas T(n) jest rzędu O(n log n). Liczba porównań w algorytmie sortowania przez scalanie jest rzędu O(n log n).

|T(n)    c*n                   c*n
|       /   \                /     \
|   T(n/2)  T(n/2)      c*n/2       c*n/2
|                      /    \       /    \
|                  T(n/4) T(n/4) T(n/4) T(n/4)
|
|             c*n  ............................ c*n
|            /    \
|       c*n/2       c*n/2  .................... c*n
|      /    \       /    \
|  c*n/4  c*n/4  c*n/4  c*n/4  ................ c*n
|  /  \   /  \   /  \   /  \
|
|  | | | | | | | | | | | | | | | |
|  c c c c c c c c c c c c c c c c  ........... c*n
|
| Drzewo będzie miało log(n)+1 poziomów, a suma wyrazów
| z każdego poziomu wynosi c*n.

KOMENTARZE

Naturalne sortowanie przez scalanie potrafi wykorzystać naturalnie istniejące podciągi posortowane, przez co można zredukować liczbę przebiegów scalania [por. timsort]. Dane posortowane nie będą wymagały w ogóle scalania.

Algorytm mergesort daje się łatwo zrównoleglić z uwagi na zastosowanie techniki dziel i zwyciężaj [CLRS]. Zrównolegla się nie tylko rekurencyjny podział na listy, ale także etap scalania. Wtedy dla n procesorów czas sortowania jest O(log n).