Sortieren & Suchen

log₂ einer Billion ist vierzig — deshalb lohnt es sich fast überall, Daten in Ordnung zu halten, statt sie später wieder und wieder linear zu durchsuchen.

Als Nächstes empfohlen → Datenstrukturen · CS·KI

Der Beitrag

Quicksort entstand 1960 in Moskau. Tony Hoare, 26-jähriger britischer Doktorand, arbeitete dort an einem Russisch-Englisch-Übersetzungssystem; die Aufgabe dahinter war das Sortieren russischer Wörterbucheinträge. Sein Verfahren — einen Pivot wählen, das Array um ihn herum aufteilen, auf beiden Seiten rekursiv weitermachen — braucht im Mittel O(n log n) und gehört über sechzig Jahre später noch immer zu den meistgenutzten Allzweck-Sortierverfahren im Produktionscode. Aus derselben Zeit stammen Mergesort (von Neumann, 1945) und Heapsort (Williams, 1964); die binäre Suche stand erst 1962 korrekt in veröffentlichtem Code, nachdem mehrere Fassungen an Off-by-One-Fehlern gescheitert waren. Donald Knuth räumte diesen Algorithmen einen ganzen Band von The Art of Computer Programming ein (Band 3, 1973) — und ein Nachschlagewerk zum Sortieren aus den 1960er Jahren hilft einem arbeitenden Programmierer heute noch weiter.

Am Sortieren wird die O-Notation zum ersten Mal handgreiflich. Die naiven Verfahren — Bubble, Selection, Insertion — liegen bei O(n²); bei einer Million Einträgen sind das 10^12 Operationen und damit Stunden. Für vergleichsbasiertes Sortieren gibt es eine bewiesene untere Schranke von O(n log n), und der Beweis ist ein Abzählargument: Jeder Vergleich liefert höchstens ein Bit Information, zu unterscheiden sind aber n! Permutationen. Mergesort und Heapsort halten diese Schranke auch im schlechtesten Fall ein, Quicksort nur im Mittel — bei unglücklicher Pivot-Wahl fällt es auf O(n²) zurück, weshalb Produktionsumsetzungen den Pivot auswürfeln. Dieselbe Million Einträge kostet unter n log n rund 20 Millionen Operationen, also einen Sekundenbruchteil. Wer Struktur in den Daten ausnutzen darf, kommt noch darunter: Counting Sort und Radix Sort vergleichen gar nicht erst. Beim Suchen dasselbe Bild — linear O(n), binär auf einem sortierten Array O(log n). Entscheidend ist, wie unfassbar träge log n wächst: log₂ einer Billion ist gerade einmal 40. Deshalb sind sortierte Datenstrukturen überall; Ordnung zu halten kostet weit weniger, als immer wieder linear durch Unsortiertes zu laufen. Hashtabellen erreichen im Mittel sogar O(1), zahlen dafür aber mit dem Verlust jeder Ordnung, und die Wahl zwischen sortiertem Array mit binärer Suche und Hashtabelle gehört zu den häufigsten Performance-Entscheidungen des Fachs. Dazu die Standardvarianten: externes Sortieren, wenn die Daten nicht in den Hauptspeicher passen; paralleles Sortieren über Tausende Maschinen; stabile gegen instabile Verfahren, je nachdem ob gleiche Schlüssel ihre Reihenfolge behalten; und adaptive Verfahren, die auf teilweise sortierten Eingaben schneller werden — Timsort etwa, die Voreinstellung in Python und Java.

Warum jetztWas heutige Produktionssprachen voreingestellt haben, ist meist Timsort — Pythons list.sort() und Javas Arrays.sort() —, 2002 von Tim Peters eingeführt. Timsort mischt Mergesort mit Insertionsort und nutzt aus, dass reale Daten fast immer schon Läufe geordneter Abschnitte enthalten; auf echten Eingaben schlägt es reines Quicksort und ist obendrein stabil, was Quicksort nicht ist. Die richtige Produktionssortierung ist also das Ergebnis von vierzig Jahren Feinschliff, nicht der Algorithmus, der im Lehrbuch zuerst drankommt. Anfrageplaner in Datenbanken wägen zwischen Sort-then-Merge, Hash-Join und Index-Lookup ab. Suchmaschinen sind im Kern riesige Probleme mit invertierten Indizes, deren Datenstrukturen von Knuths TAOCP Band 3 abstammen. Und die Vektorsuche — approximative Nächste-Nachbarn-Suche in hochdimensionalen Embedding-Räumen, mit HNSW, LSH und IVF-Indizes — ist die aktuelle Front und trägt als Datenstruktur jedes retrieval-augmentierte LLM-System.