Sortowanie przez scalanie

🎯 Po co Ci to?

W zadaniu 6.3/2 padło zdanie-zapowiedź: kto zamienia tylko sąsiadów, ten nie zejdzie poniżej liczby inwersji — czyli poniżej $n^2$ w pechowych danych. Żeby sortować szybciej, trzeba przenosić elementy daleko jednym ruchem. Jak? Odpowiedź przyszła w 1945 roku od Johna von Neumanna i jest wzorcowym dzieckiem strategii „dziel i zwyciężaj" z działu 1: potnij, posortuj połówki, scal. Sortowanie przez scalanie to pierwszy algorytm tej książki z kosztem $n \log n$ — i wzór, na którym zrozumiesz, skąd taka klasa w ogóle się bierze.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • scalić dwie posortowane listy w jedną (technika dwóch palców);
  • zapisać rekurencyjne sortowanie przez scalanie i prześledzić je na drzewie;
  • wyprowadzić koszt $O(n \log n)$ z obrazka „poziomy × praca na poziomie".

🔁 Przypomnij sobie

Z 1.4: dziel i zwyciężaj — potnij problem, rozwiąż kawałki, sklej; z 4.3: rekurencja z przypadkiem bazowym; z 2.7: liczba połowień $n$ to $\log_2 n$.

📘 Wyjaśnienie

Serce algorytmu: scalanie. Załóż, że masz dwie już posortowane listy. Połączenie ich w jedną posortowaną jest zaskakująco tanie — technika dwóch palców: postaw palec na początku każdej listy, przepisuj do wyniku mniejszy z dwóch wskazywanych elementów i przesuwaj tamten palec; gdy jedna lista się skończy, przepisz resztę drugiej:

def scal(A, B):
    wynik = []
    i, j = 0, 0                      # dwa palce
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            wynik.append(A[i]); i += 1
        else:
            wynik.append(B[j]); j += 1
    wynik.extend(A[i:])              # resztki (co najwyżej jedna lista niepusta)
    wynik.extend(B[j:])
    return wynik

(extend dokleja całą listę; A[i:] to „ogon od $i$"; += to skrót i = i + 1.) Koszt scalania: każdy element jest przepisany dokładnie raz — liniowo względem sumy długości. Zauważ też <= zamiast <: przy równych elementach pierwszeństwo ma lewa lista — to zapewnia stabilność (6.4/3).

Cały algorytm: trzy linijki logiki. Lista krótsza niż dwa elementy jest posortowana (przypadek bazowy). Dłuższą potnij na pół, posortuj połówki tym samym sposobem, scal:

def scalanie(L):
    if len(L) <= 1:
        return L
    srodek = len(L) // 2
    lewa = scalanie(L[:srodek])      # L[:s] to pierwsze s elementów
    prawa = scalanie(L[srodek:])
    return scal(lewa, prawa)

Rekurencja robi tu dokładnie to, co u Euklidesa (4.2), a nie to, co u naiwnego Fibonacciego (4.3): każde wywołanie dostaje inne, mniejsze dane — żaden podproblem się nie powtarza. Drzewo wywołań jest zdrowe.

Skąd $n \log n$? Z obrazka. Narysuj drzewo cięć: cała lista, pod nią dwie połówki, pod nimi cztery ćwiartki… aż do jedynek — a potem scalanie skleja poziomy z powrotem:

52471326254713262457123612234567praca: 8praca: 8praca: 8start3 poziomy scaleń × 8 przepisań = n·log₂n pracy
Drzewo sortowania przez scalanie dla ośmiu elementów: trzy poziomy cięcia na połówki i scalanie w górę; na każdym poziomie łączna praca to n operacji, poziomów jest log n. · rys. własny

Rachunek z obrazka: poziomów jest tyle, ile połowień $n$ do jedynek — $\log_2 n$ (2.7!). Na każdym poziomie scalanie przepisuje łącznie wszystkie $n$ elementów (kawałki są różne, ale suma długości stała). Praca = poziomy × praca poziomu = $n \log_2 n$. Dla miliona: $10^6 \cdot 20 = 2 \cdot 10^7$ — dwadzieścia milionów zamiast pół biliona z bąbelkowego. To nie usprawnienie; to inna epoka.

I rzecz najgłębsza: ten koszt jest gwarantowany — scalanie w ogóle nie ma najgorszego przypadku (dane złośliwe, losowe, posortowane: zawsze $n \log n$). Płaci za to pamięcią: scal buduje nowe listy, więc potrzebuje drugiego egzemplarza danych. Gwarancja za pamięć — pierwszy wielki handel tej jednostki; drugi zawrze quicksort.

💭 Pomyśł: Da się sortować porównaniami szybciej niż $n \log n$? Intuicja z 2.7: sortowanie musi rozróżnić wszystkie możliwe kolejności $n$ elementów — a jest ich $n!$. Ile porównań (pytań tak/nie) trzeba, żeby rozróżnić $n!$ możliwości?

Sprawdź odpowiedź

Każde porównanie to jedno pytanie tak/nie, więc (2.7!) trzeba ich co najmniej $\log_2(n!)$ — a to w przybliżeniu $n \log_2 n$ (bo $n!$ ma około $n \log n$ bitów). Wniosek-bomba: żadne sortowanie porównaniami nie zejdzie poniżej $n \log n$ w najgorszym przypadku — scalanie jest (z dokładnością do stałej) optymalne, a poszukiwania „sortowania w $O(n)$" można odwołać. To drugi w tej książce (po 6.1) dowód niemożliwości — i znów zaoszczędzi komuś życie zmarnowane na szukanie perpetuum mobile. (Furtka: sortowania bez porównań, znające naturę danych — np. zliczanie małych liczb całkowitych — potrafią zejść niżej; dział 9 wspomni o leksykograficznym.)

🧮 Prześledź

scalanie([38, 27, 43, 3]): rozpisz pełne drzewo — cięcia w dół, scalenia w górę, z wynikami scal na każdym poziomie.

Sprawdź odpowiedź

Cięcia: [38,27,43,3] → [38,27] i [43,3] → [38],[27],[43],[3]. Scalenia: scal([38],[27]) = [27,38] (1 porównanie); scal([43],[3]) = [3,43] (1); scal([27,38],[3,43]): 3<27 → 3; 27<43 → 27; 38<43 → 38; resztka 43 → [3,27,38,43] (3 porównania). Razem 5 porównań przy górnej granicy $n \log n = 8$. Zwróć uwagę na resztkę: gdy jedna lista się wyczerpie, ogon drugiej wchodzi bez porównań — stąd praktyczne koszty bywają niższe od wzoru.

⚠️ Uwaga, pułapka

Najczęstszy błąd implementacji: przypadek bazowy len(L) <= 1. Napisz < 1 (albo zapomnij w ogóle), a scalanie([x]) potnie listę na [] i [x]… i będzie ciąć puste listy w nieskończoność — rekurencyjny odpowiednik pętli wiecznej, zakończony błędem głębokości. Reguła z 4.3 obowiązuje bez taryfy ulgowej: fundament przed piętrami — przypadek bazowy pisz i testuj najpierw (scalanie([]), scalanie([5])).

🛠️ Teraz Ty

Bez komputera: narysuj pełne drzewo dla [5, 2, 4, 7, 1, 3, 2, 6] (8 elementów — trzy poziomy jak na rycinie) i policz porównania wszystkich scaleń. Z komputerem: zaimplementuj scal i scalanie, przetestuj na brzegach (pusta, jednoelementowa, z duplikatami, odwrócona), a potem urządź derby z wstawianiem na liście losowej $n = 10,000$ — liczniki porównań obu stron na stół.

📐 Definicje tej lekcji

  • Scalanie (dwóch posortowanych) — technika dwóch palców; liniowe; <= daje stabilność.
  • Sortowanie przez scalanie — potnij na pół, posortuj rekurencyjnie, scal; $O(n \log n)$ zawsze, kosztem dodatkowej pamięci.
  • Dolna granica sortowania — porównaniami nie da się szybciej niż $\log_2(n!) \approx n \log_2 n$ w najgorszym przypadku.

📌 Najważniejsze w pigułce

  • Tanie jest scalanie posortowanych — cały algorytm to pomysł „doprowadź do sytuacji, gdzie zostało samo scalanie".
  • Koszt z obrazka: $\log n$ poziomów × $n$ pracy = $n \log n$, bez najgorszego przypadku, za cenę pamięci.
  • Poniżej $n \log n$ porównaniami zejść się nie da — to dolna granica, nie brak pomysłu.

🎒 Zadania

  1. Scal ręcznie A = [2, 9, 11] z B = [3, 5, 12, 14], notując ruchy palców i liczbę porównań.
Wskazówka i odpowiedź

2<3→2; 3<9→3; 5<9→5; 9<12→9; 11<12→11; A wyczerpana → resztka [12,14] bez porównań. Wynik [2,3,5,9,11,12,14], 5 porównań na 7 elementów. Maksimum porównań przy scalaniu list $a$ i $b$ elementów to $a + b - 1$ (ostatni element wchodzi bez pytania) — sprawdź, że tu nie zostało osiągnięte i dlaczego.

  1. Ile poziomów ma drzewo scalania dla $n$ = 1000? Ile łącznie operacji przepisywania wykona algorytm? Porównaj z liczbą porównań bąbelkowego z 6.3.
Wskazówka i odpowiedź

Poziomów $\lceil \log_2 1000 \rceil = 10$; przepisań ~$1000 \times 10 = 10,000$. Bąbelkowe: $\frac{1000 \cdot 999}{2} \approx 500,000$ porównań — pięćdziesiąt razy więcej. A przy milionie elementów stosunek rośnie do dwudziestu pięciu tysięcy razy: przewaga klasy $n \log n$ nad $n^2$ rośnie z danymi — to definicja „lepszej klasy" z 6.5 w liczbach.

  1. Masz 100 posortowanych list po 1000 elementów (wyniki ze stu szkół). Zaproponuj sposób scalenia ich w jeden ranking i oszacuj koszt: (a) scalaj po kolei do rosnącego wyniku, (b) scalaj parami „turniejowo". Który plan lepszy?
Wskazówka i odpowiedź

(a) Wynik rośnie: 1000+1000, potem 2000+1000, 3000+1000… — łącznie $\sum_{k=1}^{99} (k \cdot 1000 + 1000) \approx 5$ mln przepisań. (b) Turniej: 50 scaleń par (koszt $10^5$), 25 scaleń (2×), … — każdy poziom turnieju przepisuje wszystkie $10^5$ elementów, poziomów $\log_2 100 \approx 7$ → ~$7 \cdot 10^5$. Turniej wygrywa siedmiokrotnie — bo to dokładnie drzewo scalania, tylko startujące z gotowych liści. Struktura drzewa bije kolejkę — zapamiętaj do działu 9 (kopiec zrobi to samo jeszcze wygodniej).

🔍 Sprawdź, czy umiesz

  • Scalić dwie posortowane listy na kartce techniką dwóch palców.
  • Narysować drzewo scalania i wyprowadzić z niego $n \log n$.
  • Wyjaśnić handel „gwarancja za pamięć" i dolną granicę sortowania.

Ucz się tej jednostki z asystentem