Dziel i zwyciężaj: Merge, Quick, Heap, Tree, IntroSort i TimSort

W pierwszej części skończyliśmy na sortowaniu Shella, czyli na pomyśle, że warto porównywać elementy odległe od siebie. Teraz idziemy o poziom wyżej: zamiast poprawiać przestawianie sąsiadów, podzielimy problem na mniejsze. Wszystkie algorytmy z tego wpisu mają O(n log n) w przypadku średnim – i mimo to każdy z nich jest inny w sposób, który widać gołym okiem w animacji.

Sortowanie przez scalanie

Merge sort opisał John von Neumann w 1945 roku i przez osiemdziesiąt lat nikt nie znalazł w tym pomyśle dziury. Podziel tablicę na pół, posortuj każdą połowę rekurencyjnie, a potem scal dwie posortowane listy w jedną, biorąc zawsze mniejszy z dwóch elementów na wierzchu.

# Python
def merge_sort(data):
    """Klasyczne scalanie zstępujące: dziel na pół, sortuj połowy, scalaj."""
    if len(data) <= 1:
        return list(data)
    middle = len(data) // 2
    left = merge_sort(data[:middle])
    right = merge_sort(data[middle:])
    return merge(left, right)


def merge(left, right):
    """Scalanie dwóch posortowanych list; <= zamiast < decyduje o stabilności."""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # przy remisie bierzemy z LEWEJ – to jest stabilność
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Cały algorytm mieści się w jednym warunku: left[i] <= right[j]. Zamień <= na <, a stracisz stabilność – przy równych kluczach zaczniesz brać element z prawej połowy, czyli ten, który pierwotnie stał dalej. Tyle wystarczy, żeby posortowana wcześniej lista rozjechała się przy drugim sortowaniu.

Scalanie ma trzy cechy, których nie ma nikt inny w tym zestawie: jest stabilne, ma gwarantowane O(n log n) także w pesymistycznym przypadku i nie potrzebuje dostępu swobodnego – wystarczy mu odczyt sekwencyjny. Dlatego to jedyny algorytm z tej listy, którym da się posortować listę jednokierunkową albo plik większy niż pamięć operacyjna (sortowanie zewnętrzne, do którego wrócimy w czwartej części).

Ceną jest pamięć: O(n) na bufor. Istnieją warianty scalające w miejscu, ale wszystkie płacą za to sporym mnożnikiem czasu – i praktycznie nikt ich nie używa poza bibliotekami, które muszą mieć twardą gwarancję pamięci.

Sortowanie szybkie

Quicksort, pomysł Tony’ego Hoare’a z 1959 roku, odwraca kolejność: najpierw robi trudną robotę, potem dzieli. Wybierasz element rozdzielający (pivot), przestawiasz tablicę tak, żeby po lewej stronie były elementy mniejsze, a po prawej większe, i rekurencyjnie sortujesz obie części. Scalania nie ma – po podziale wszystko już jest na swoim miejscu.

# Python
def quick_sort(items, lo=0, hi=None):
    """Quicksort w miejscu z podziałem Lomuto (pivot na końcu zakresu)."""
    if hi is None:
        hi = len(items) - 1
    if lo >= hi:
        return items
    split = partition(items, lo, hi)
    quick_sort(items, lo, split - 1)
    quick_sort(items, split + 1, hi)
    return items


def partition(items, lo, hi):
    """Przerzuca mniejsze od pivota na lewo; zwraca ostateczną pozycję pivota."""
    pivot = items[hi]
    boundary = lo
    for i in range(lo, hi):
        if items[i] < pivot:
            items[boundary], items[i] = items[i], items[boundary]
            boundary += 1
    items[boundary], items[hi] = items[hi], items[boundary]
    return boundary

Quicksort sortuje w miejscu (jedyna pamięć to stos rekurencji, O(log n) przy sensownych podziałach), świetnie współpracuje z pamięcią podręczną procesora, bo pracuje na ciągłych fragmentach tablicy, i dzięki temu w praktyce bije sortowanie przez scalanie mimo identycznej asymptotyki. W naszym wyścigu z części pierwszej quicksort zrobił więcej porównań niż scalanie (296 do 208) i mimo to przyjechał wcześniej – bo scalanie musi jeszcze przepisać całą tablicę z bufora.

Ma jednak jedną słabość, i to poważną.

Przypadek pesymistyczny na żywo

Jeśli pivot systematycznie wypada na skraju, podział nie dzieli niczego na pół: jedna strona ma n−1 elementów, druga zero. Wtedy quicksort degeneruje się do O(n²). Najprostszy sposób, żeby to zobaczyć, to podać mu tablicę posortowaną odwrotnie – przy pivocie z końca zakresu każdy podział jest maksymalnie niesprawiedliwy.

Na tablicy odwróconej quicksort z tego kodu robi 1128 porównań, czyli dokładnie tyle, co sortowanie bąbelkowe. Scalanie – 128. TimSort – 47, bo w ogóle rozpoznaje, że dane są jedną malejącą serią, odwraca ją i kończy. To najlepsza możliwa reklama tego, dlaczego biblioteki nie używają czystego quicksorta.

Ratunek to wybór pivota:

• Mediana z trzech – bierzemy pierwszy, środkowy i ostatni element, a pivotem robimy środkowy z nich. Kosztuje trzy porównania i likwiduje degenerację na danych posortowanych i odwróconych.
• Pivot losowy – żaden konkretny układ danych nie jest już zły „na zawsze”, ale pechowe losowanie dalej jest możliwe.
• Mediana median (algorytm BFPRT) – gwarantuje dobry podział i O(n log n) w pesymistycznym przypadku, ale stała jest tak duża, że nikt nie używa go w praktyce.
• Dwa pivoty – tablica dzielona na trzy części naraz. Tak działa Arrays.sort dla typów prostych w Javie: dokumentacja mówi wprost o Dual-Pivot Quicksort Yaroslavskiego, Bentleya i Blocha.

# Python
def median_of_three(items, lo, hi):
    """Pivot = mediana z pierwszego, środkowego i ostatniego; potem na koniec zakresu."""
    mid = (lo + hi) // 2
    a, b, c = items[lo], items[mid], items[hi]
    if (a <= b <= c) or (c <= b <= a):
        best = mid
    elif (b <= a <= c) or (c <= a <= b):
        best = lo
    else:
        best = hi
    items[best], items[hi] = items[hi], items[best]
    return items[hi]

Sortowanie przez kopcowanie

Heapsort to sortowanie przez wybieranie, któremu ktoś dał porządną strukturę danych. Zamiast szukać maksimum liniowo, trzymamy dane w kopcu binarnym – drzewie zapisanym w tej samej tablicy, w którym rodzic jest zawsze większy od dzieci. Maksimum jest wtedy na pozycji zerowej i wyciąga się je w czasie stałym, a naprawa kopca kosztuje O(log n).

# Python
def heap_sort(items):
    """Buduj kopiec (O(n)), potem n razy zdejmij maksimum na koniec tablicy."""
    n = len(items)
    for start in range(n // 2 - 1, -1, -1):
        sift_down(items, start, n)
    for end in range(n - 1, 0, -1):
        items[0], items[end] = items[end], items[0]   # maksimum na swoje miejsce
        sift_down(items, 0, end)                      # napraw kopiec bez ostatniego elementu
    return items


def sift_down(items, root, size):
    """Przesuwa element w dół kopca, dopóki któreś dziecko jest większe."""
    while True:
        left, right = 2 * root + 1, 2 * root + 2
        largest = root
        if left < size and items[left] > items[largest]:
            largest = left
        if right < size and items[right] > items[largest]:
            largest = right
        if largest == root:
            return
        items[root], items[largest] = items[largest], items[root]
        root = largest

Heapsort ma dokładnie te cechy, których brakuje quicksortowi: gwarantowane O(n log n) i sortowanie w miejscu bez rekurencji. Nie ma za to stabilności, a w praktyce jest wolniejszy od quicksorta o stały czynnik, bo skacze po tablicy w sposób nieprzyjazny dla pamięci podręcznej (rodzic i dziecko dzieli odległość rzędu wielkości połowy tablicy). W otwierającym wyścigu z pierwszej części heapsort wykonał 387 porównań i aż 462 zapisy – najwięcej ze wszystkich algorytmów O(n log n).

Dlatego heapsort rzadko bywa głównym algorytmem, a bardzo często – awaryjnym. Zaraz zobaczymy, gdzie.

Sortowanie drzewiaste

Skoro kopiec pomógł, to może pomoże drzewo BST? Tree sort wstawia kolejno wszystkie elementy do drzewa poszukiwań binarnych, a potem robi obchód in-order, który wypisuje je w kolejności rosnącej.

# Python
class Node:
    __slots__ = ("value", "left", "right")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def tree_sort(data):
    """Wstaw wszystko do BST, potem obchód in-order daje kolejność rosnącą."""
    root = None
    for value in data:
        root = insert(root, value)
    return list(in_order(root))


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)   # >= idzie w prawo, więc sort jest stabilny
    return node


def in_order(node):
    if node is not None:
        yield from in_order(node.left)
        yield node.value
        yield from in_order(node.right)

W animacji widać coś ciekawego: przez pierwszą fazę tablica w ogóle się nie rusza – bo cała praca dzieje się w drzewie obok. Dopiero obchód zapisuje wynik, słupek po słupku, od razu w docelowej kolejności (48 zapisów na 48 elementów, czyli minimum).

Tree sort ma jednak dokładnie ten sam problem, co quicksort, i to nie przez przypadek: oba wykonują te same porównania. Kolejne wstawienia do BST odpowiadają kolejnym wyborom pivota. Jeśli dane przychodzą posortowane, drzewo degeneruje się do listy i mamy O(n²) – w wyścigu na tablicy odwróconej tree sort zrobił te same 1128 porównań co quicksort. Ratunkiem są drzewa samorównoważące (AVL, czerwono-czarne), ale wtedy płacimy za rotacje i całość staje się wyraźnie wolniejsza od kopca.

Praktyczny sens tree sortu jest inny niż sortowanie tablicy raz: jeśli dane napływają i przez cały czas chcesz mieć do nich dostęp w kolejności posortowanej, drzewo (albo kopiec) jest właściwą odpowiedzią, a sortowanie tablicy od zera – nie.

IntroSort: quicksort, który wie, kiedy przestać

Skoro quicksort jest szybki, ale zawodny, heapsort wolniejszy, ale niezawodny, a wstawianie najlepsze na krótkich fragmentach – David Musser w 1997 roku zaproponował, żeby po prostu użyć wszystkich trzech. IntroSort (introspective sort) zaczyna jak quicksort, liczy głębokość rekurencji i:

• gdy fragment ma mniej niż kilkanaście elementów – kończy sortowaniem przez wstawianie,
• gdy głębokość przekroczy 2·log₂(n) – przełącza ten fragment na heapsort,
• w pozostałych przypadkach robi zwykły podział.

# Python
from math import log2

def intro_sort(items):
    """Quicksort z limitem głębokości; kopcowanie jako plan B, wstawianie na końcówki."""
    _intro(items, 0, len(items) - 1, 2 * int(log2(max(2, len(items)))))
    return items


def _intro(items, lo, hi, depth):
    while lo < hi:
        if hi - lo + 1 <= 16:                 # krótki fragment: wstawianie jest tańsze
            insertion_range(items, lo, hi)
            return
        if depth == 0:                        # podziały się nie udały: gwarantowane O(n log n)
            heap_range(items, lo, hi)
            return
        depth -= 1
        split = partition(items, lo, hi)
        if split - lo < hi - split:           # krótszą połowę rekurencyjnie, dłuższą w pętli
            _intro(items, lo, split - 1, depth)
            lo = split + 1
        else:
            _intro(items, split + 1, hi, depth)
            hi = split - 1

To nie jest ciekawostka akademicka – tak działa std::sort w C++. Standard wymaga od niego O(N log N) w przypadku pesymistycznym (od C++11 to twardy wymóg, wcześniej była to tylko wartość średnia), a nikt nie zna szybszej metody spełnienia tego wymogu niż hybryda z awaryjnym kopcem. Sortowanie z biblioteki standardowej C++ nie jest stabilne; od stabilności jest osobne std::stable_sort, które w zamian potrzebuje pamięci na bufor.

TimSort: algorytm napisany pod prawdziwe dane

Wszystkie dotychczasowe algorytmy zakładają najgorsze: że dane są całkowicie losowe. Tim Peters w 2002 roku zauważył, że prawdziwe dane takie nie są. Listy, które sortujemy w programach, składają się zwykle z fragmentów już uporządkowanych – posklejanych logów, dopisanych rekordów, wyników po części posortowanych. TimSort buduje na tym cały algorytm:

1. Przejdź tablicę i wykryj naturalne serie (runs) – ciągi rosnące lub malejące. Malejące odwróć w miejscu (dlatego dane odwrócone kosztują go n−1 porównań i nic więcej).
2. Zbyt krótkie serie dociągnij do długości minrun (32–64) sortowaniem przez wstawianie z wyszukiwaniem binarnym.
3. Odkładaj serie na stos i scalaj je według reguły, która pilnuje, żeby scalane fragmenty miały zbliżoną długość.
4. Przy scalaniu, gdy jedna seria systematycznie wygrywa, przejdź w tryb galopowania: zamiast porównywać element po elemencie, szukaj miejsca wstawienia skokami wykładniczymi.

Powyżej te same trzy algorytmy na tablicy prawie posortowanej – takiej, jaka najczęściej trafia do prawdziwego sort(). TimSort: 195 porównań. Scalanie: 198, ale przy 272 zapisach zamiast 176. Quicksort: 299 porównań, bo jego podziały nic nie zyskują na wstępnym uporządkowaniu danych.

Efektem jest algorytm stabilny, o gwarantowanym O(n log n), liniowy na danych już posortowanych i zaskakująco odporny na typowe układy rzeczywiste. Kosztem jest bufor O(n) i implementacja, która w CPythonie zajmuje ponad tysiąc linii razem z komentarzami – w tym słynny plik Objects/listsort.txt, czyli kilkanaście stron notatek Petersa o tym, dlaczego każda decyzja wygląda tak, a nie inaczej. To jedna z najlepszych lektur w całym repozytorium CPythona.

TimSort trafił z Pythona do Javy (Arrays.sort dla obiektów, wprost oznaczone w dokumentacji jako adaptacja kodu Petersa), do Androida, do V8 i do Swifta. A w samym Pythonie od wersji 3.11 jego reguła scalania została podmieniona na jeszcze lepszą – ale to już temat na czwartą część cyklu.

Podsumowanie

Wszystkie te algorytmy porównują elementy parami – i wszystkie zatrzymują się na tej samej granicy O(n log n). W trzeciej części zobaczymy, skąd ta granica się bierze, dlaczego jest nieprzekraczalna i jak trzy algorytmy przechodzą pod nią suchą stopą – nie porównując niczego.