Tony Hoare, 26-jähriger britischer Doktorand, erfand Quicksort 1960, während er auf die Kompilierung eines Russisch-Englisch-Übersetzungssystems wartete. Die Ausgangsaufgabe war, russische Wörterbucheinträge zu sortieren. Hoares Algorithmus — Pivot wählen, das Array um ihn herum aufteilen, auf jeder Seite rekursieren — läuft im Mittel in O(n log n) und ist fünfundsechzig Jahre später noch immer der meistverwendete Allzweck-Sortieralgorithmus in Produktionscode. Aus derselben Zeit stammen Mergesort (von Neumann, 1945), Heapsort (Williams, 1964) und die binäre Suche, die in veröffentlichtem Code erst 1962 korrekt umgesetzt war, nachdem mehrere Versionen an Off-by-One-Fehlern gescheitert waren. Donald Knuth widmete diesen Algorithmen einen ganzen Band von The Art of Computer Programming (Band 3, 1973); ein Nachschlagewerk zum Sortieren aus den 1960er Jahren leistet einem arbeitenden Programmierer heute noch gute Dienste.
Sortieren ist die kanonische Stelle, an der Big-O konkret greifbar wird. Naives Sortieren — Bubble, Selection, Insertion — liegt bei O(n²). Bei einer Million Einträgen sind das 10^12 Operationen, also Stunden Arbeit. Vergleichsbasiertes Sortieren hat eine bewiesene untere Schranke von O(n log n): mehr als ein Bit Information pro Vergleich ist nicht zu holen, und n! Permutationen müssen unterschieden werden — weniger als n log n Vergleiche im schlechtesten Fall gehen also nicht. Mergesort und Heapsort erreichen diese Schranke im schlechtesten Fall; Quicksort erreicht sie im Mittel — im schlechtesten Fall bei schlechter Pivot-Wahl O(n²), weshalb Produktionsumsetzungen den Pivot zufällig wählen. Für eine Million Einträge sind n log n nur rund 20 Millionen Operationen, ein Sekundenbruchteil. Nicht-vergleichende Verfahren (Counting Sort, Radix Sort) schlagen O(n log n), indem sie Struktur in den Daten ausnutzen. Suche: lineare Suche ist O(n), binäre Suche auf einem sortierten Array O(log n). Die zentrale Einsicht ist, wie außerordentlich langsam log n wächst — log₂ einer Billion ist gerade einmal 40. Genau deshalb sind sortierte Datenstrukturen überall: die Kosten, Ordnung zu halten, liegen weit unter denen wiederholter linearer Suche im Unsortierten. Hashtabellen erreichen im Mittel O(1), indem sie die Ordnung aufgeben. Die Wahl zwischen sortiertem Array mit binärer Suche und Hashtabelle ist eine der häufigsten Performance-Entscheidungen überhaupt. Standardvarianten: externes Sortieren (Daten zu groß für den Hauptspeicher), paralleles Sortieren über Tausende Maschinen, stabile gegen instabile Verfahren (ob die Reihenfolge gleicher Schlüssel erhalten bleibt) und adaptive Sortierverfahren, die auf teilweise sortierten Eingaben schneller sind — Timsort, die Voreinstellung in Python und Java.
Die Standardsortierung moderner Produktionssprachen ist meist Timsort (Pythons list.sort(), Javas Arrays.sort()), 2002 von Tim Peters eingeführt. Timsort verbindet Mergesort und Insertionsort und nutzt natürlich vorkommende Läufe bereits sortierter Daten; es ist auf realen Eingaben schneller als reines Quicksort und obendrein stabil — Quicksort ist es nicht. Die richtige Produktionssortierung ist das Ergebnis von vierzig Jahren praktischer Verfeinerung, nicht der Algorithmus, der im Lehrbuch zuerst kommt. Datenbank-Anfrageplaner entscheiden zwischen Sort-then-Merge, Hash-Join und Index-Lookup. Suchmaschinen sind im Kern gewaltige Invertierter-Index-Probleme; ihre Datenstrukturen sind Nachfahren von Knuths TAOCP Band 3. Die Vektorsuche — approximative Nearest-Neighbour-Suche in hochdimensionalen Embedding-Räumen (HNSW, LSH, IVF-Indizes) — ist die heutige Front und das datenstrukturelle Fundament jedes retrieval-augmentierten LLM-Systems.