Jak sortuje twój język: TimSort, Powersort, pdqsort i reszta

Przez trzy części cyklu pisaliśmy algorytmy sortowania od zera, dzieliliśmy i zwyciężali, a nawet obeszliśmy granicę n log n. Czas na pytanie, które ma realne znaczenie w pracy: co dzieje się naprawdę, gdy wywołujesz wbudowany sort? Odpowiedź jest ciekawsza, niż się wydaje – bo w każdym z popularnych języków siedzi tam inna hybryda, a w jednym przypadku poprawna odpowiedź zmieniła się kilka lat temu i mało kto to zauważył.

Python: TimSort, ale już nie do końca

list.sort() i sorted() używają TimSorta – algorytmu, który Tim Peters napisał dla CPythona w 2002 roku i który stamtąd rozszedł się po świecie. Sortowanie w Pythonie jest stabilne – i to gwarancja dana w dokumentacji, a nie szczegół implementacji.

Ale od CPythona 3.11 odpowiedź „Python używa TimSorta” jest już tylko w połowie prawdziwa. Reguła decydująca o tym, które serie i w jakiej kolejności scalać, została wymieniona na Powersort Munro i Wilda – strategię, która jest dowodliwie bliska optymalnej względem entropii rozkładu długości serii. Reszta maszynerii (wykrywanie serii, minrun, galopowanie, sortowanie wstawianiem krótkich fragmentów) została bez zmian. W Objects/listsort.txt stoi to wprost: the code now uses the „powersort” merge strategy.

Dla większości programów nic się nie zmieniło. Różnica jest widoczna dopiero na danych, na których stara reguła zachowywała się wyjątkowo źle – i to jest zresztą typowe dla tej rodziny usprawnień: nie chodzi o przyspieszenie przypadku średniego, tylko o usunięcie przypadków patologicznych.

# Python
people = [("Kowalski", "IT", 30), ("Nowak", "HR", 25), ("Abacki", "IT", 25)]

people.sort(key=lambda person: person[2])     # najpierw klucz mniej ważny: wiek
people.sort(key=lambda person: person[1])     # potem ważniejszy: dział
# stabilność sprawia, że w każdym dziale kolejność wg wieku zostaje zachowana

by_age_desc = sorted(people, key=lambda person: person[2], reverse=True)
# reverse=True NIE odwraca kolejności elementów równych – stabilność obowiązuje także tu

Trzy rzeczy, o których warto pamiętać w praktyce:

• key= liczone jest raz na element, a nie przy każdym porównaniu. To wbudowana wersja sztuczki znanej jako dekoruj-sortuj-odekoruj i dlatego key= jest zawsze szybsze niż functools.cmp_to_key z własnym komparatorem.
• sorted() zwraca nową listę, list.sort() sortuje w miejscu i zwraca None. Ten drugi jest oszczędniejszy pamięciowo i o kilka procent szybszy.
• reverse=True to nie to samo co sorted(...)[::-1] – odwrócenie posortowanej listy zamieni kolejność elementów równych, a reverse=True ją zachowa.

Java: dwa różne algorytmy w tej samej metodzie

Java ma najciekawszy podział w całym zestawieniu, bo Arrays.sort to w istocie dwie różne implementacje wybierane po typie argumentu:

• Typy proste (int[], double[]…) – Dual-Pivot Quicksort Vladimira Yaroslavskiego, Jona Bentleya i Joshuy Blocha. Dokumentacja wprost obiecuje O(n log n) i to, że jest zwykle szybszy niż klasyczny quicksort z jednym pivotem. Stabilność nie ma tu znaczenia: dwie liczby 5 są nierozróżnialne, więc nie ma czego psuć.
• Obiekty (Object[], List<T>, Collections.sort) – TimSort, opisany w dokumentacji jako adaptacja kodu Tima Petersa. Stabilny, adaptacyjny, z buforem do n/2 referencji.

Z tego wyboru wynika najbardziej znany komunikat błędu w historii sortowania:

// Java
java.lang.IllegalArgumentException: Comparison method violates its general contract!

To nie jest błąd biblioteki, tylko sygnał, że twój komparator jest niespójny – na przykład zwraca a < b i jednocześnie b < a, albo używa odejmowania na dużych liczbach i przepełnia int. TimSort, w przeciwieństwie do prostszych algorytmów, potrafi to wykryć, bo opiera swoje scalanie na założeniu o przechodniości porządku. Prosty quicksort w takiej sytuacji po prostu zwróciłby śmieci.

C++: introsort z gwarancją w standardzie

std::sort to IntroSort – quicksort z awaryjnym kopcowaniem i sortowaniem przez wstawianie dla krótkich fragmentów, opisany w części drugiej. Od C++11 standard wymaga od niego O(N log N) porównań w przypadku pesymistycznym (wcześniej wymóg dotyczył tylko przypadku średniego, co formalnie dopuszczało degenerację quicksorta).

std::sort nie jest stabilny. Od stabilności jest std::stable_sort, który w zamian potrzebuje bufora – a gdy pamięci brakuje, przechodzi na wolniejszy wariant O(N log²N).

Biblioteka standardowa C++ ma przy tym coś, czego brakuje większości języków – rodzinę sortowań częściowych:

// C++
std::partial_sort(v.begin(), v.begin() + 10, v.end());   // 10 najmniejszych, posortowanych
std::nth_element(v.begin(), v.begin() + n / 2, v.end()); // mediana bez pełnego sortowania

std::nth_element to implementacja quickselect (introselect): działa średnio w czasie liniowym, bo po podziale schodzi tylko do tej połowy, w której leży szukana pozycja. Jeśli potrzebujesz mediany albo dziesięciu największych elementów, sortowanie całości jest marnowaniem czasu – i to jest chyba najważniejsza praktyczna lekcja z całego cyklu.

JavaScript: pułapka, o którą potyka się każdy

// JavaScript
[1, 10, 2, 21].sort();          // [1, 10, 2, 21]  <- to nie błąd przeglądarki
[1, 10, 2, 21].sort((a, b) => a - b);   // [1, 2, 10, 21]

Domyślny komparator Array.prototype.sort zamienia elementy na napisy i porównuje je leksykograficznie. "10" < "2", bo znak 1 jest wcześniej niż 2. To zachowanie jest w specyfikacji od pierwszej wersji języka i nigdy nie zostanie zmienione, bo zależy od niego zbyt dużo istniejącego kodu. Wniosek: przy liczbach zawsze podawaj komparator.

Dwie dobre wiadomości z ostatnich lat:

• Od ES2019 specyfikacja wymaga, żeby sort był stabilny. Wcześniej silniki robiły, co chciały (V8 stosował quicksort dla dłuższych tablic i wyniki potrafiły się różnić między przeglądarkami). Dziś V8 – czyli Chrome, Edge i Node – używa TimSorta.
• Od ES2023 jest toSorted(), który zwraca nową tablicę zamiast mutować oryginał. To jeden z tych przypadków, w których platforma dogoniła biblioteki: kiedyś trzeba było pisać [...arr].sort(), dziś wystarczy arr.toSorted().

// JavaScript
const names = ["Żaba", "Ala", "Ćma", "Zenon"];
names.sort();                                     // porządek wg kodów UTF-16 – nie polski
names.sort(new Intl.Collator("pl").compare);      // Ala, Ćma, Zenon, Żaba

PHP: stabilność od wersji 8.0

W PHP funkcje sortujące były niestabilne do wersji 7.x włącznie. Od PHP 8.0 są stabilne – i sposób, w jaki to osiągnięto, jest pouczający: silnik nie wymienił algorytmu. Pod spodem dalej pracuje zend_sort, czyli hybrydowy, niestabilny quicksort. Stabilność uzyskano, zapamiętując pierwotną pozycję każdego elementu i używając jej jako kryterium rozstrzygającego remisy.

To ogólna technika, którą warto znać, bo działa w każdym języku i w każdej bazie danych: dowolny algorytm sortowania staje się stabilny, jeśli do klucza dokleisz pierwotny indeks jako ostatnie kryterium. Kosztem jest pamięć na indeksy i odrobina czasu na dodatkowe porównania.

<?php
// Ten sam wzorzec ręcznie – działa także na PHP 7 i w SQL (ORDER BY dzial, lp)
$indexed = [];
foreach ($rows as $i => $row) {
    $indexed[] = [$row, $i];
}
usort($indexed, fn($a, $b) => [$a[0]['dept'], $a[1]] <=> [$b[0]['dept'], $b[1]]);
$rows = array_column($indexed, 0);

O sortowaniu polskich napisów w PHP – z Collator z rozszerzenia intl zamiast ręcznego podmieniania znaków diakrytycznych – pisałem osobno w Sortowanie w PHP: analiza i optymalizacja. To jest zresztą temat, który dotyczy każdego języka: porządek alfabetyczny nie jest porządkiem kodów znaków, a reguły zależą od języka (w polskim „ł” jest osobną literą po „l”, w szwedzkim „ä” idzie po „z”).

Rust i Go: nowa fala

Rust ma dwie funkcje i uczciwie nazywa rzeczy po imieniu: sort jest stabilny i używa bufora, a sort_unstable sortuje w miejscu i jest szybszy. W wydaniu 1.81 obie implementacje wymieniono na nowsze algorytmy – szybsze i szybciej się kompilujące – a przy okazji dodano coś, czego nie ma nigdzie indziej: gdy twoja implementacja Ord jest niespójna, biblioteka panikuje, zamiast po cichu zwrócić losowo poprzestawiane dane. To ta sama diagnoza co w Javie, tylko postawiona głośniej.

Go w wersji 1.19 przepisało sort na pdqsort (pattern-defeating quicksort) – współczesnego następcę introsorta, który wykrywa typowe układy danych (już posortowane, odwrócone, z wieloma duplikatami) i obsługuje je w czasie liniowym, a przy złych podziałach przechodzi na heapsort. Ten sam algorytm stoi dziś za sort_unstable w Ruście i za sortowaniem w kilku bibliotekach C++.

Podsumowanie: ściągawka

Kiedy w ogóle nie sortować

Na koniec cztery sytuacje, w których najlepszym algorytmem sortowania jest jego brak:

1. Potrzebujesz kilku największych elementów. heapq.nlargest(10, data) w Pythonie, std::partial_sort w C++, ORDER BY ... LIMIT 10 w SQL. Kopiec o rozmiarze k daje O(n log k) zamiast O(n log n).
2. Potrzebujesz mediany albo k-tego elementu. Quickselect – std::nth_element, numpy.partition – działa średnio liniowo.
3. Dane napływają i cały czas mają być uporządkowane. Wtedy właściwą odpowiedzią jest struktura danych: kopiec, drzewo, bisect.insort na liście, a w bazie – indeks. Indeks to nic innego jak trwale utrzymany porządek, dzięki któremu ORDER BY po indeksowanej kolumnie nie sortuje niczego.
4. Dane są większe niż pamięć. Wtedy wchodzi sortowanie zewnętrzne: podziel plik na porcje mieszczące się w RAM, posortuj każdą, zapisz na dysk i scal je wielodrożnie (k-way merge). Dokładnie to robi uniksowy sort(1), gdy podasz mu plik o wielkości kilkudziesięciu gigabajtów – i dlatego jest to jedyny algorytm z całego cyklu, który zwykły użytkownik systemu uruchamia świadomie.

Na tym kończymy cykl. Jeśli miałbym z niego zostawić trzy zdania: algorytm sortowania w twoim języku jest prawie na pewno lepszy od tego, który napiszesz; jego wybór to hybryda podejmująca decyzje w trakcie działania, a nie jeden klasyczny algorytm z podręcznika; a największe przyspieszenie i tak zwykle daje nie zmiana algorytmu, tylko zauważenie, że sortowanie nie było w tym miejscu potrzebne.