Sortierverfahren

Unter einem Sortierverfahren versteht man in der Informatik einen Algorithmus, der dazu dient, ein Tupel (i. Allg. ein Array) zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist („kleiner-gleich“), z. B. die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. ⓘ

Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten bezüglich der Zeitkomplexität (Anzahl der nötigen Operationen) sowie der Platzkomplexität (zusätzlich zum Eingabe-Array benötigter weiterer Speicherplatz). Die Komplexität eines Algorithmus wird üblicherweise in der Landau-Notation dargestellt (s. u. Ausdrücke wie $\Theta (n\cdot \log(n))$). Die Zeitkomplexität hängt bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bei günstigster „Vorsortierung“), Average Case (Normalfall) und Worst Case (schlechtester Fall ~ die Werte sind „maximal ungünstig vorgeordnet“). Häufig sind zusätzliche Faktoren zu beachten, die Einfluss auf Zeit- oder Platzkomplexität haben, zum Beispiel langsamer Zugriff auf extern liegende Daten, begrenzte Größe des Arbeitsspeichers oder ähnliches. ⓘ

Man unterscheidet zudem zwischen stabilen und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren dies nicht garantieren. Ist beispielsweise die Mitarbeiterliste einer Firma nach Nachname geordnet und wird anschließend nach Alter (in Jahren) sortiert, so bleibt die (Nachnamen-)Reihenfolge unter gleichaltrigen Mitarbeitern bei einem stabilen Sortierverfahren bestehen. ⓘ

Zudem unterscheidet man zwischen Sortierverfahren, die in-place (auch in situ) arbeiten, d. h. der zusätzliche Speicherbedarf ist unabhängig von der Anzahl der zu sortierenden Elemente (also konstant und meist gering), und solchen, bei denen er abhängig ist (out-of-place oder ex situ). ⓘ

Und man unterscheidet auch zwischen natürlichen Sortierverfahren, die bei vorsortierten Daten schneller arbeiten als bei unsortierten Daten, und solchen, die es nicht tun. Algorithmen, bei denen der Kontrollfluss von den Daten abhängt, nennt man adaptiv und dementsprechend Sortierverfahren, die nicht von den Eingabedaten abhängen, nicht-adaptiv. Nicht-adaptive Algorithmen sind demnach besonders interessant für Hardware-Implementierungen. ⓘ

Manuelles Sortieren (etwa von Karteikarten) sowie elektro-mechanische Sortierverfahren (z. B. für Lochkarten) entsprechen meist einem der hier beschriebenen softwarebasierten Sortierverfahren, oder Mischtypen. ⓘ

Formal muss die Ausgabe jedes Sortieralgorithmus zwei Bedingungen erfüllen:

1. Die Ausgabe erfolgt in monotoner Reihenfolge (jedes Element ist nicht kleiner/größer als das vorherige Element, entsprechend der erforderlichen Reihenfolge).
2. Die Ausgabe ist eine Permutation (eine Umordnung, bei der jedoch alle ursprünglichen Elemente erhalten bleiben) der Eingabedaten. ⓘ

Um eine optimale Effizienz zu erzielen, sollten die Eingabedaten in einer Datenstruktur gespeichert werden, die einen zufälligen Zugriff ermöglicht, und nicht in einer, die nur einen sequentiellen Zugriff zulässt. ⓘ

Geschichte und Konzepte

Seit den Anfängen der Informatik wurde das Sortierproblem intensiv erforscht, was vielleicht darauf zurückzuführen ist, dass es trotz seiner einfachen und vertrauten Aussage schwierig ist, es effizient zu lösen. Zu den Autoren der ersten Sortieralgorithmen um 1951 gehörte Betty Holberton, die an ENIAC und UNIVAC arbeitete. Bubble Sort wurde bereits 1956 analysiert. Asymptotisch optimale Algorithmen sind seit Mitte des 20. Jahrhunderts bekannt - und es werden immer noch neue Algorithmen erfunden, wobei das weit verbreitete Timsort aus dem Jahr 2002 stammt und das Library Sort 2006 erstmals veröffentlicht wurde. ⓘ

Vergleichssortieralgorithmen benötigen grundsätzlich Ω(n log n) Vergleiche (einige Eingabesequenzen erfordern ein Vielfaches von n log n Vergleichen, wobei n die Anzahl der Elemente in dem zu sortierenden Array ist). Algorithmen, die nicht auf Vergleichen basieren, wie z. B. Counting Sort, können eine bessere Leistung aufweisen. ⓘ

Sortieralgorithmen sind in einführenden Informatikkursen weit verbreitet, wo die Fülle von Algorithmen für dieses Problem eine sanfte Einführung in eine Vielzahl von Kernalgorithmuskonzepten bietet, wie z. B. Big-O-Notation, Divide-and-Conquer-Algorithmen, Datenstrukturen wie Heaps und binäre Bäume, randomisierte Algorithmen, Best-, Worst- und Average-Case-Analyse, Zeit-Raum-Abwägungen sowie obere und untere Schranken. ⓘ

Das optimale Sortieren kleiner Arrays (mit den wenigsten Vergleichen und Vertauschungen) oder das schnelle Sortieren (d.h. unter Berücksichtigung maschinenspezifischer Details) ist immer noch ein offenes Forschungsproblem, wobei Lösungen nur für sehr kleine Arrays (<20 Elemente) bekannt sind. Auch die optimale (nach verschiedenen Definitionen) Sortierung auf einer Parallelmaschine ist ein offenes Forschungsthema. ⓘ

Klassifizierung

Sortieralgorithmen können klassifiziert werden nach:

• Rechnerische Komplexität
  • Bestes, schlechtestes und durchschnittliches Verhalten in Bezug auf die Größe der Liste. Bei typischen seriellen Sortieralgorithmen ist das gute Verhalten O(n log n), bei paralleler Sortierung O(log² n) und das schlechte Verhalten O(n²). Das ideale Verhalten für eine serielle Sortierung ist O(n), aber dies ist im durchschnittlichen Fall nicht möglich. Optimales paralleles Sortieren ist O(log n).
  • Swaps für "in-place"-Algorithmen.
• Speichernutzung (und Nutzung anderer Computerressourcen). Insbesondere einige Sortieralgorithmen sind "in-place". Streng genommen benötigt eine In-Place-Sortierung nur O(1) Speicher über die zu sortierenden Elemente hinaus; manchmal wird O(log n) zusätzlicher Speicher als "In-Place" betrachtet.
• Rekursion: Einige Algorithmen sind entweder rekursiv oder nicht rekursiv, während andere beides sein können (z. B. Merge Sort).
• Stabilität: Stabile Sortieralgorithmen behalten die relative Reihenfolge von Datensätzen mit gleichen Schlüsseln (d. h. Werten) bei.
• Ob es sich um eine Vergleichssortierung handelt oder nicht. Bei einer Vergleichssortierung werden die Daten nur durch den Vergleich zweier Elemente mit einem Vergleichsoperator untersucht.
• Allgemeine Methode: Einfügen, Austausch, Auswahl, Zusammenführen usw. Zu den Austauschsortierungen gehören Bubble Sort und Quicksort. Zu den Auswahlsortierungen gehören Cycle Sort und Heapsort.
• Ob der Algorithmus seriell oder parallel ist. Der Rest dieser Diskussion konzentriert sich fast ausschließlich auf serielle Algorithmen und geht von einem seriellen Betrieb aus.
• Anpassungsfähigkeit: Ob die Vorsortiertheit der Eingabe die Laufzeit beeinflusst oder nicht. Algorithmen, die dies berücksichtigen, werden als adaptiv bezeichnet.
• Online: Ein Algorithmus wie Insertion Sort, der online ist, kann einen konstanten Strom von Eingaben sortieren. ⓘ

Stabilität

Ein Beispiel für eine stabile Sortierung von Spielkarten. Wenn die Karten mit einer stabilen Sortierung nach Rang sortiert werden, müssen die beiden 5er in der sortierten Ausgabe in der gleichen Reihenfolge bleiben, in der sie ursprünglich waren. Wenn sie mit einer nicht stabilen Sortierung sortiert werden, können die 5er in der sortierten Ausgabe in der umgekehrten Reihenfolge erscheinen. ⓘ

Stabile Sortieralgorithmen sortieren gleiche Elemente in der gleichen Reihenfolge, in der sie in der Eingabe erscheinen. Im Beispiel der Kartensortierung auf der rechten Seite werden die Karten beispielsweise nach ihrem Rang sortiert, und ihre Farbe wird ignoriert. Auf diese Weise ist es möglich, dass mehrere verschiedene korrekt sortierte Versionen der ursprünglichen Liste entstehen. Stabile Sortieralgorithmen wählen eine davon aus, und zwar nach folgender Regel: Wenn zwei Elemente als gleichwertig verglichen werden (wie die beiden 5er-Karten), dann wird ihre relative Reihenfolge beibehalten, d. h. wenn das eine in der Eingabe vor dem anderen steht, dann steht es auch in der Ausgabe vor dem anderen. ⓘ

Stabilität ist wichtig, um die Reihenfolge über mehrere Sortierungen desselben Datensatzes hinweg zu erhalten. Nehmen wir zum Beispiel an, dass Schülerdatensätze, die aus Name und Klassenstufe bestehen, dynamisch sortiert werden, zuerst nach Name, dann nach Klassenstufe. Wenn in beiden Fällen ein stabiler Sortieralgorithmus verwendet wird, ändert die Sortierung nach Klassenstufe die Reihenfolge der Namen nicht; bei einer instabilen Sortierung könnte es sein, dass die Sortierung nach Klassenstufe die Reihenfolge der Namen durcheinander bringt, was zu einer nicht alphabetischen Liste von Schülern führt. ⓘ

Formal gesehen können die zu sortierenden Daten als Datensatz oder Tupel von Werten dargestellt werden, und der Teil der Daten, der für die Sortierung verwendet wird, wird als Schlüssel bezeichnet. In dem Beispiel mit den Karten werden die Karten als Datensatz (Rang, Farbe) dargestellt, und der Schlüssel ist der Rang. Ein Sortieralgorithmus ist stabil, wenn immer dann, wenn es zwei Datensätze R und S mit demselben Schlüssel gibt und R vor S in der ursprünglichen Liste erscheint, R immer vor S in der sortierten Liste erscheint. ⓘ

Wenn gleiche Elemente ununterscheidbar sind, wie z. B. bei ganzen Zahlen oder allgemeiner bei allen Daten, bei denen das gesamte Element der Schlüssel ist, ist Stabilität kein Thema. Stabilität ist auch kein Problem, wenn alle Schlüssel unterschiedlich sind. ⓘ

Instabile Sortieralgorithmen können speziell implementiert werden, um stabil zu sein. Eine Möglichkeit besteht darin, den Schlüsselvergleich künstlich zu erweitern, so dass Vergleiche zwischen zwei Objekten mit ansonsten gleichen Schlüsseln unter Verwendung der Reihenfolge der Einträge in der ursprünglichen Eingabeliste als Gleichheitsentscheid entschieden werden. Das Erinnern an diese Reihenfolge kann jedoch zusätzliche Zeit und zusätzlichen Platz erfordern. ⓘ

Eine Anwendung für stabile Sortieralgorithmen ist das Sortieren einer Liste mit einem Primär- und einem Sekundärschlüssel. Nehmen wir zum Beispiel an, wir möchten ein Kartenblatt so sortieren, dass die Farben in der Reihenfolge Kreuz (♣), Karo (♦), Herz (♥), Pik (♠) sind, und innerhalb jeder Farbe sind die Karten nach Rang sortiert. Dazu werden die Karten zunächst nach Rang sortiert (mit einer beliebigen Sortierung) und dann stabil nach Farbe sortiert:

Innerhalb jeder Farbe behält die stabile Sortierung die bereits vorgenommene Sortierung nach Rang bei. Diese Idee kann auf eine beliebige Anzahl von Schlüsseln ausgedehnt werden und wird von der Radix-Sortierung verwendet. Der gleiche Effekt kann mit einer instabilen Sortierung durch einen lexikografischen Schlüsselvergleich erzielt werden, der z. B. zuerst nach Farbe und dann nach Rang vergleicht, wenn die Farben gleich sind. ⓘ

Vergleich von Algorithmen

In diesen Tabellen steht n für die Anzahl der zu sortierenden Datensätze. Die Spalten "Beste", "Durchschnitt" und "Schlechteste" geben die jeweilige Zeitkomplexität an, unter der Annahme, dass die Länge jedes Schlüssels konstant ist und daher alle Vergleiche, Vertauschungen und anderen Operationen in konstanter Zeit durchgeführt werden können. "Speicher" bezeichnet den zusätzlichen Speicherbedarf, der zusätzlich zu dem von der Liste selbst verwendeten Speicherplatz benötigt wird, unter der gleichen Annahme. Die angegebenen Laufzeiten und der Speicherbedarf stehen in der Notation big O, so dass die Basis der Logarithmen keine Rolle spielt. Die Schreibweise log² n bedeutet (log n)². ⓘ

Vergleichssortierungen

Nachstehend finden Sie eine Tabelle mit Vergleichssortierungen. Eine Vergleichssortierung kann im Durchschnitt nicht besser als O(n log n) sein. ⓘ

Vergleichssortierungen

Name	Beste	Durchschnittlich	Schlechteste	Speicher	Stabil	Methode	Andere Anmerkungen ⓘ
Quicksort	$n\log n$	$n\log n$	$n^{2}$	$\log n$	Keine	Partitionierung	Quicksort wird in der Regel in-place mit O(log n) Stapelplatz durchgeführt.
Merge-Sortierung	$n\log n$	$n\log n$	$n\log n$	n	Ja	Zusammenführen	Hochgradig parallelisierbar (bis zu O(log n) unter Verwendung des Algorithmus der drei Ungarn).
In-Place-Merge-Sortierung	—	—	$n\log ^{2}n$	1	Ja	Zusammenführen	Kann als stabile Sortierung auf der Grundlage von stabilem In-Place-Merging implementiert werden.
Introsort	$n\log n$	$n\log n$	$n\log n$	$\log n$	Keine	Partitionierung und Auswahl	Wird in mehreren STL-Implementierungen verwendet.
Heapsort	$n\log n$	$n\log n$	$n\log n$	1	Keine	Auswahl
Einfügungs-Sortierung	n	$n^{2}$	$n^{2}$	1	Ja	Einfügung	O(n + d), im schlimmsten Fall über Sequenzen, die d Invertierungen haben.
Blocksortierung	n	$n\log n$	$n\log n$	1	Ja	Einfügung & Zusammenführung	Kombinieren Sie einen blockbasierten $O(n)$ In-Place-Merge-Algorithmus mit einer Bottom-Up-Merge-Sortierung.
Timsort	n	$n\log n$	$n\log n$	n	Ja	Einfügung & Zusammenführung	Führt n-1 Vergleiche durch, wenn die Daten bereits sortiert oder umgekehrt sortiert sind.
Auswahlsortierung	$n^{2}$	$n^{2}$	$n^{2}$	1	Keine	Auswahl	Stabile mit $O(n)$ zusätzlichem Platz, wenn verknüpfte Listen verwendet werden oder wenn eine Variante von Insertion Sort anstelle des Vertauschens der beiden Elemente durchgeführt wird.
Cubesort	n	$n\log n$	$n\log n$	n	Ja	Einfügung	Führt n-1 Vergleiche durch, wenn die Daten bereits sortiert oder umgekehrt sortiert sind.
Shellsort	$n\log n$	$n^{4/3}$	$n^{3/2}$	1	Keine	Einfügung	Geringe Codegröße.
Bubble-Sortierung	n	$n^{2}$	$n^{2}$	1	Ja	Austauschen	Winzige Codegröße.
Austausch-Sortierung	$n^{2}$	$n^{2}$	$n^{2}$	1	Keine	Austauschen	Winzige Codegröße.
Baum-Sortierung	$n\log n$	$n\log n$	$n\log n$(ausgeglichen)	n	Ja	Einfügung	Bei Verwendung eines selbstbalancierenden binären Suchbaums.
Zyklische Sortierung	$n^{2}$	$n^{2}$	$n^{2}$	1	Keine	Auswahl	In-place mit theoretisch optimaler Anzahl von Schreibvorgängen.
Bibliothekssortierung	$n\log n$	$n\log n$	$n^{2}$	n	Keine	Einfügung	Ähnlich wie eine Gapped-Insertion-Sortierung. Sie erfordert eine zufällige Permutation der Eingabe, um mit hoher Wahrscheinlichkeit Zeitschranken zu gewährleisten, was sie nicht stabil macht.
Geduldiges Sortieren	n	$n\log n$	$n\log n$	n	Keine	Einfügung & Auswahl	Findet alle längsten ansteigenden Teilsequenzen in O(n log n).
Glättende Sortierung	n	$n\log n$	$n\log n$	1	Keine	Auswahl	Eine adaptive Variante der Heapsortierung, die eher auf der Leonardo-Sequenz als auf einem traditionellen binären Heap basiert.
Strangsortierung	n	$n^{2}$	$n^{2}$	n	Ja	Auswahl
Turnier-Sortierung	$n\log n$	$n\log n$	$n\log n$	n	Keine	Auswahl	Variante von Heapsort.
Cocktailshaker-Sortierung	n	$n^{2}$	$n^{2}$	1	Ja	Austauschen	Eine Variante von Bubblesort, die gut mit kleinen Werten am Ende der Liste umgehen kann.
Kamm-Sortierung	$n\log n$	$n^{2}$	$n^{2}$	1	Keine	Austauschen	Im Durchschnitt schneller als Bubblesort.
Gnom-Sortierung	n	$n^{2}$	$n^{2}$	1	Ja	Austauschen	Winzige Codegröße.
Ungerade-gerade Sortierung	n	$n^{2}$	$n^{2}$	1	Ja	Austauschen	Kann leicht auf parallelen Prozessoren ausgeführt werden.

Nicht-Vergleichssortierungen

Die folgende Tabelle beschreibt ganzzahlige Sortieralgorithmen und andere Sortieralgorithmen, die keine Vergleichssortierungen sind. Als solche sind sie nicht auf Ω(n log n) beschränkt. Die nachstehenden Komplexitäten gehen von n zu sortierenden Elementen aus, wobei die Schlüssel die Größe k, die Ziffern die Größe d und r den Bereich der zu sortierenden Zahlen haben. Viele von ihnen beruhen auf der Annahme, dass die Schlüsselgröße groß genug ist, damit alle Einträge eindeutige Schlüsselwerte haben, und dass daher n ≪ 2k ist, wobei ≪ "viel weniger als" bedeutet. Im Modell der Zufallszugriffsmaschine mit Einheitskosten können Algorithmen mit Laufzeiten von $\scriptstyle n\cdot {\frac {k}{d}}$wie z. B. Radix-Sortierung, immer noch Zeit proportional zu Θ(n log n), da n auf nicht mehr als $2^{\frac {k}{d}}$und eine größere Anzahl zu sortierender Elemente würde ein größeres k erfordern, um sie im Speicher zu speichern. ⓘ

Nicht-Vergleichssortierungen

Name	Beste	Durchschnittlich	Schlechteste	Speicher	Stabil	n ≪ 2k	Anmerkungen ⓘ
Schubladensortierung	—	$n+2^{k}$	$n+2^{k}$	$2^{k}$	Ja	Ja	Kann keine Nicht-Ganzzahlen sortieren.
Eimersortierung (einheitliche Schlüssel)	—	$n+k$	$n^{2}\cdot k$	$n\cdot k$	Ja	Keine	Setzt eine gleichmäßige Verteilung der Elemente aus dem Bereich im Array voraus. Kann auch keine Nicht-Ganzzahlen sortieren.
Eimersortierung (ganzzahlige Schlüssel)	—	$n+r$	$n+r$	$n+r$	Ja	Ja	Wenn r gleich $O(n)$ist, dann ist die durchschnittliche Zeitkomplexität $O(n)$.
Zählende Sortierung	—	$n+r$	$n+r$	$n+r$	Ja	Ja	Wenn r gleich $O(n)$ist, dann ist die durchschnittliche Zeitkomplexität $O(n)$.
LSD-Radix-Sortierung	$n$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Ja	Keine	${\frac {k}{d}}$ Rekursionsebenen, 2d für Count-Array. Im Gegensatz zu den meisten Verteilungssortierungen können damit Fließkommazahlen, negative Zahlen und mehr sortiert werden.
MSD-Radix-Sortierung	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Ja	Keine	Stabile Version verwendet ein externes Array der Größe n, um alle Bins zu speichern. Wie die LSD-Variante kann sie auch Nicht-Ganzzahlen sortieren.
MSD-Radix-Sortierung (in-place)	—	$n\cdot {\frac {k}{1}}$	$n\cdot {\frac {k}{1}}$	$2^{1}$	Keine	Keine	d=1 für In-Place, $k/1$ Rekursionsstufen, kein Zählfeld.
Spreadsort	n	$n\cdot {\frac {k}{d}}$	$n\cdot \left({{\frac {k}{s}}+d}\right)$	${\frac {k}{d}}\cdot 2^{d}$	Keine	Keine	Asymptotisch basiert auf der Annahme, dass n ≪ 2k, aber der Algorithmus erfordert dies nicht.
Burstsort	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	Keine	Keine	Hat einen besseren konstanten Faktor als Radixsort für die Sortierung von Zeichenketten. Hängt jedoch etwas von den Besonderheiten häufig vorkommender Zeichenketten ab.
Blitzsortierung	n	$n+r$	$n^{2}$	n	Keine	Keine	Erfordert eine gleichmäßige Verteilung der Elemente aus dem Bereich im Array, um in linearer Zeit zu laufen. Wenn die Verteilung extrem schief ist, kann es quadratisch werden, wenn die zugrundeliegende Sortierung quadratisch ist (normalerweise ist es eine Einfügesortierung). Die In-Place-Version ist nicht stabil.
Postman-Sortierung	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	—	Keine	Eine Variante von Bucket Sort, die sehr ähnlich wie MSD Radix Sort funktioniert. Speziell für Postdienstanforderungen.

Samplesort kann zur Parallelisierung jeder der Nicht-Vergleichssortierungen verwendet werden, indem die Daten effizient in mehrere Buckets verteilt werden und dann die Sortierung an mehrere Prozessoren weitergegeben wird, ohne dass eine Zusammenführung erforderlich ist, da die Buckets bereits untereinander sortiert sind. ⓘ

Andere

Einige Algorithmen sind im Vergleich zu den oben genannten langsam, wie z. B. Bogosort mit unbegrenzter Laufzeit und Stooge-Sort mit O(n^2.7) Laufzeit. Diese Sortierungen werden in der Regel zu Lehrzwecken beschrieben, um zu zeigen, wie die Laufzeit von Algorithmen geschätzt wird. In der folgenden Tabelle werden einige Sortieralgorithmen beschrieben, die für den realen Einsatz in herkömmlichen Softwarekontexten aufgrund extrem schlechter Leistung oder spezieller Hardwareanforderungen unpraktisch sind. ⓘ

Name	Beste	Durchschnittlich	Schlechteste	Speicher	Stabil	Vergleich	Andere Anmerkungen ⓘ
Perlensortierung	n	S	S	$n^{2}$	—	Keine	Funktioniert nur mit positiven ganzen Zahlen. Erfordert spezielle Hardware, um in garantierter Zeit zu laufen. $O(n)$ Zeit zu laufen. Es gibt eine Möglichkeit der Software-Implementierung, aber die Laufzeit wird $O(S)$wobei S die Summe aller zu sortierenden ganzen Zahlen ist, im Falle kleiner ganzer Zahlen kann sie als linear angesehen werden.
Einfache Pfannkuchensortierung	—	$n^{2}$	$n^{2}$	$\log n$	Keine	Ja	Count ist die Anzahl der Umdrehungen.
"Ich kann nicht glauben, dass es geht"-Sortierung	$n^{2}$	$n^{2}$	$n^{2}$	1	Keine	Ja	Bemerkenswert ist vor allem, dass es sich um eine fehlerhafte Implementierung von Insertion Sort oder Exchange Sort zu handeln scheint.
Spaghetti-Sortierung (Umfrage)	n	n	n	$n^{2}$	Ja	Abfrage	Dies ist ein analoger Algorithmus zum Sortieren einer Folge von Elementen in linearer Zeit, der O(n) Stapelplatz benötigt, und die Sortierung ist stabil. Dies erfordert n parallele Prozessoren. Siehe Spaghetti-Sortierung#Analyse.
Sortier-Netzwerk	Unterschiedlich	Unterschiedlich	Unterschiedlich	Unterschiedlich	Unterschiedlich (stabile Sortiernetze erfordern mehr Vergleiche)	Ja	Die Reihenfolge der Vergleiche wird im Voraus auf der Grundlage einer festen Netzgröße festgelegt.
Bitonischer Sortierer	$\log ^{2}n$ parallel	$\log ^{2}n$ parallel	$n\log ^{2}n$ nicht-parallel	1	Keine	Ja	Eine effektive Variante von Sortiernetzwerken.
Bogosort	n	$(n\times n!)$	unbeschränkt (sicher), $(n\times n!)$ (erwartet)	1	Keine	Ja	Zufälliges Mischen. Wird nur als Beispiel verwendet, da selbst die erwartete Best-Case-Laufzeit furchtbar ist.
Stooge-Sortierung	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	n	Keine	Ja	Langsamer als die meisten Sortieralgorithmen (auch naive) mit einer Zeitkomplexität von O(nlog 3 / log 1.5 ) = O(n2.7095...) Kann stabilisiert werden und ist ebenfalls ein Sortiernetzwerk.
Slowsort	$n^{\log n}$	$n^{\log n}$	$n^{\log n}$	n	Keine	Ja	Ein Multiplikations- und Übergabealgorithmus, gleichbedeutend mit einem Divide-and-Conquer-Algorithmus.

Theoretische Informatiker haben andere Sortieralgorithmen detailliert beschrieben, die unter der Annahme zusätzlicher Beschränkungen eine bessere Zeitkomplexität als O(n log n) bieten, darunter:

• Thorups Algorithmus, ein randomisierter Algorithmus zum Sortieren von Schlüsseln aus einem Bereich endlicher Größe, der O(n log log n) Zeit und O(n) Raum benötigt.
• Ein randomisierter ganzzahliger Sortieralgorithmus, der $O\left(n{\sqrt {\log \log n}}\right)$ erwartete Zeit und O(n) Platz benötigt. ⓘ

Beliebte Sortieralgorithmen

Es gibt zwar eine große Anzahl von Sortieralgorithmen, aber in der praktischen Umsetzung überwiegen einige wenige Algorithmen. Für kleine Datensätze wird häufig die Einfügesortierung verwendet, während für große Datensätze eine asymptotisch effiziente Sortierung verwendet wird, vor allem Heapsort, Merge-Sort oder Quicksort. Effiziente Implementierungen verwenden im Allgemeinen einen hybriden Algorithmus, der einen asymptotisch effizienten Algorithmus für die Gesamtsortierung mit einer Einfügesortierung für kleine Listen am Ende einer Rekursion kombiniert. Hochentwickelte Implementierungen verwenden anspruchsvollere Varianten wie Timsort (Merge-Sort, Insertion-Sort und zusätzliche Logik), die in Android, Java und Python verwendet werden, und Introsort (Quicksort und Heapsort), die (in abgewandelter Form) in einigen C++-Sortierimplementierungen und in .NET verwendet werden. ⓘ

Für eingeschränktere Daten, z. B. Zahlen in einem festen Intervall, werden häufig Verteilungssortierungen wie Zählsortierung oder Radixsortierung verwendet. Bubble Sort und Varianten werden in der Praxis selten verwendet, sind aber in der Lehre und in theoretischen Diskussionen häufig anzutreffen. ⓘ

Beim physischen Sortieren von Objekten (z. B. beim Alphabetisieren von Papieren, Tests oder Büchern) verwenden Menschen intuitiv in der Regel Einfügungssortierungen für kleine Mengen. Bei größeren Mengen wird oft zuerst nach dem Anfangsbuchstaben sortiert, und die Mehrfachsortierung ermöglicht die praktische Sortierung sehr großer Mengen. Oft ist der Platz relativ günstig, z. B. wenn man die Objekte auf dem Boden oder über eine große Fläche verteilt, aber die Operationen sind teuer, insbesondere wenn man ein Objekt über eine große Entfernung bewegt - die Lokalität der Referenz ist wichtig. Merge-Sortierungen sind auch für physische Objekte praktisch, zumal zwei Hände benutzt werden können, eine für jede zu mischende Liste, während andere Algorithmen, wie Heapsort oder Quicksort, für den menschlichen Gebrauch schlecht geeignet sind. Andere Algorithmen, wie z. B. Library Sort, eine Variante von Insertion Sort, die Leerzeichen hinterlässt, sind ebenfalls für den physischen Gebrauch geeignet. ⓘ

Einfache Sortierungen

Zwei der einfachsten Sortierverfahren sind die Einfüge- und die Auswahlsortierung, die beide aufgrund des geringen Overheads bei kleinen Datenmengen effizient sind, aber bei großen Datenmengen nicht effizient. Die Einfügesortierung ist in der Praxis im Allgemeinen schneller als die Auswahlsortierung, da weniger Vergleiche durchgeführt werden müssen und die Leistung bei fast sortierten Daten gut ist. ⓘ

Einfügungs-Sortierung

Einfügungssortierung ist ein einfacher Sortieralgorithmus, der für kleine Listen und meist sortierte Listen relativ effizient ist und oft als Teil von komplexeren Algorithmen verwendet wird. Dabei werden die Elemente einer Liste einzeln entnommen und an der richtigen Stelle in eine neue sortierte Liste eingefügt, ähnlich wie wir Geld in unsere Brieftasche stecken. In Arrays können sich die neue Liste und die verbleibenden Elemente den Platz des Arrays teilen, aber das Einfügen ist teuer, da alle folgenden Elemente um eins verschoben werden müssen. Shellsort ist eine Variante der Einfügesortierung, die für größere Listen effizienter ist. ⓘ

Auswahlsortierung

Selection sort ist eine Vergleichssortierung an Ort und Stelle. Sie hat eine Komplexität von O(n²), was sie bei großen Listen ineffizient macht, und schneidet im Allgemeinen schlechter ab als die ähnliche Einfügesortierung. Selection sort zeichnet sich durch seine Einfachheit aus und hat in bestimmten Situationen auch Leistungsvorteile gegenüber komplizierteren Algorithmen. ⓘ

Der Algorithmus findet den kleinsten Wert, vertauscht ihn mit dem Wert an der ersten Position und wiederholt diese Schritte für den Rest der Liste. Er führt nicht mehr als n Vertauschungen durch und ist daher nützlich, wenn die Vertauschung sehr teuer ist. ⓘ

Effiziente Sortierungen

Praktische allgemeine Sortieralgorithmen basieren fast immer auf einem Algorithmus mit einer durchschnittlichen Zeitkomplexität (und im Allgemeinen einer Worst-Case-Komplexität) von O(n log n), von denen die gängigsten Heapsort, Merge Sort und Quicksort sind. Jeder dieser Algorithmen hat Vor- und Nachteile, wobei der wichtigste darin besteht, dass eine einfache Implementierung von Merge Sort O(n) zusätzlichen Platz benötigt und eine einfache Implementierung von Quicksort im schlimmsten Fall eine Komplexität von O(n²) aufweist. Diese Probleme können auf Kosten eines komplexeren Algorithmus gelöst oder verbessert werden. ⓘ

Während diese Algorithmen bei Zufallsdaten asymptotisch effizient sind, werden für die praktische Effizienz bei realen Daten verschiedene Änderungen vorgenommen. Erstens wird der Overhead dieser Algorithmen bei kleineren Daten beträchtlich, so dass oft ein hybrider Algorithmus verwendet wird, der üblicherweise auf Insertion Sort umschaltet, sobald die Daten klein genug sind. Zweitens schneiden die Algorithmen bei bereits sortierten oder fast sortierten Daten oft schlecht ab - diese sind in realen Daten üblich und können mit geeigneten Algorithmen in O(n)-Zeit sortiert werden. Schließlich können sie auch instabil sein, und Stabilität ist oft eine wünschenswerte Eigenschaft bei einer Sortierung. Daher werden oft ausgefeiltere Algorithmen verwendet, wie z. B. Timsort (basierend auf Merge Sort) oder Introsort (basierend auf Quicksort, das auf Heapsort zurückgreift). ⓘ

Merge-Sortierung

Die Merge-Sortierung macht sich die Einfachheit zunutze, mit der bereits sortierte Listen zu einer neuen sortierten Liste zusammengeführt werden können. Zunächst werden jeweils zwei Elemente miteinander verglichen (z. B. 1 mit 2, dann 3 mit 4...) und vertauscht, wenn das erste Element nach dem zweiten kommen sollte. Anschließend wird jede der so entstandenen Zweierlisten zu einer Viererliste zusammengeführt, dann werden die Viererlisten zusammengeführt und so weiter, bis schließlich zwei Listen zur endgültigen sortierten Liste zusammengeführt werden. Von den hier beschriebenen Algorithmen ist dies der erste, der sich gut auf sehr große Listen skalieren lässt, da seine Laufzeit im schlimmsten Fall O(n log n) beträgt. Er kann auch leicht auf Listen und nicht nur auf Arrays angewendet werden, da er nur sequentiellen Zugriff erfordert, nicht aber zufälligen Zugriff. Sie hat jedoch eine zusätzliche O(n)-Platzkomplexität und erfordert bei einfachen Implementierungen eine große Anzahl von Kopien. ⓘ

Merge-Sort hat in jüngster Zeit einen Popularitätsschub für praktische Implementierungen erfahren, was auf seine Verwendung im anspruchsvollen Algorithmus Timsort zurückzuführen ist, der in den Programmiersprachen Python und Java (ab JDK7) als Standardsortierroutine verwendet wird. Merge-Sort selbst ist die Standardroutine u. a. in Perl und wird in Java mindestens seit 2000 in JDK1.3 verwendet. ⓘ

Heapsort

Heapsort ist eine viel effizientere Version von Selection Sort. Auch hier wird das größte (oder kleinste) Element der Liste bestimmt, an das Ende (oder den Anfang) der Liste gesetzt und dann mit dem Rest der Liste fortgefahren, aber diese Aufgabe wird durch die Verwendung einer Datenstruktur namens Heap, einer speziellen Art von Binärbaum, effizient erledigt. Sobald die Datenliste zu einem Heap gemacht wurde, ist der Wurzelknoten garantiert das größte (oder kleinste) Element. Wenn er entfernt und an das Ende der Liste gesetzt wird, wird der Heap neu geordnet, so dass das größte verbleibende Element an die Wurzel rückt. Die Suche nach dem nächstgrößeren Element dauert mit dem Heap O(log n) statt O(n) für eine lineare Suche wie bei der einfachen Auswahlsortierung. Dadurch kann Heapsort in O(n log n)-Zeit ausgeführt werden, und dies ist auch der ungünstigste Fall der Komplexität. ⓘ

Quicksort

Quicksort ist ein Divide-and-Conquer-Algorithmus, der auf einer Partitionsoperation beruht: Um ein Array zu partitionieren, wird ein Pivot genanntes Element ausgewählt. Alle Elemente, die kleiner sind als das Pivot-Element, werden vor das Pivot-Element verschoben und alle Elemente, die größer sind, werden hinter das Pivot-Element verschoben. Dies kann effizient in linearer Zeit und an Ort und Stelle geschehen. Die kleineren und größeren Teillisten werden dann rekursiv sortiert. Dies führt zu einer durchschnittlichen Zeitkomplexität von O(n log n) mit geringem Overhead und ist daher ein beliebter Algorithmus. Effiziente Implementierungen von Quicksort (mit In-Place-Partitionierung) sind typischerweise instabile Sortierungen und etwas komplex, gehören aber in der Praxis zu den schnellsten Sortieralgorithmen. Zusammen mit seinem bescheidenen Platzbedarf von O(log n) ist Quicksort einer der beliebtesten Sortieralgorithmen und ist in vielen Standardprogrammierbibliotheken verfügbar. ⓘ

Ein wichtiger Vorbehalt bei Quicksort ist, dass seine Leistung im schlimmsten Fall O(n²) beträgt. Dies ist zwar selten, aber bei naiven Implementierungen (Auswahl des ersten oder letzten Elements als Pivot) tritt dies bei sortierten Daten häufig auf. Das komplexeste Problem bei Quicksort ist also die Wahl eines guten Pivot-Elements, da eine durchgängig schlechte Wahl von Pivots zu einer drastisch langsameren O(n²)-Leistung führen kann, während eine gute Wahl von Pivots eine O(n log n)-Leistung ergibt, die asymptotisch optimal ist. Wenn zum Beispiel bei jedem Schritt der Median als Drehpunkt gewählt wird, arbeitet der Algorithmus in O(n log n). Die Ermittlung des Medians, z. B. durch den Algorithmus zur Auswahl des Medians von Medianen, ist jedoch eine O(n)-Operation auf unsortierten Listen und verursacht daher einen erheblichen Overhead beim Sortieren. In der Praxis führt die Wahl eines zufälligen Pivots fast sicher zu einer Leistung von O(n log n). ⓘ

Shellsort

Shellsort unterscheidet sich von Bubble Sort dadurch, dass es Elemente an zahlreiche Tauschpositionen verschiebt. ⓘ

Shellsort wurde 1959 von Donald Shell erfunden. Es verbessert die Einfügesortierung, indem es Elemente, die nicht in der richtigen Reihenfolge sind, mehr als eine Position auf einmal verschiebt. Das Konzept hinter Shellsort ist, dass die Einfügesortierung in $O(kn)$ Zeit, wobei k der größte Abstand zwischen zwei verrutschten Elementen ist. Das bedeutet, dass sie im Allgemeinen in O(n²) ausgeführt werden, aber für Daten, die größtenteils sortiert sind und nur wenige Elemente an falscher Stelle enthalten, sind sie schneller. Indem man also zunächst weit entfernte Elemente sortiert und den Abstand zwischen den zu sortierenden Elementen schrittweise verkleinert, wird die endgültige Sortierung viel schneller berechnet. Eine Implementierung kann so beschrieben werden, dass die Datenfolge in einem zweidimensionalen Array angeordnet wird und dann die Spalten des Arrays mit Hilfe von Insertion Sort sortiert werden. ⓘ

Die Zeitkomplexität von Shellsort im schlimmsten Fall ist ein offenes Problem und hängt von der verwendeten Gap-Sequenz ab, wobei die bekannten Komplexitäten von O(n²) bis O(n^4/3) und Θ(n log² n) reichen. Dies und die Tatsache, dass Shellsort an Ort und Stelle ausgeführt wird, nur relativ wenig Code benötigt und nicht auf den Aufrufstapel zurückgreifen muss, macht es in Situationen nützlich, in denen der Speicherplatz knapp ist, wie z. B. in eingebetteten Systemen und Betriebssystemkerneln. ⓘ

Bubble-Sortierung und Varianten

Bubble Sort und Varianten wie Shellsort und Cocktailsort sind einfache, sehr ineffiziente Sortieralgorithmen. Sie werden aufgrund ihrer einfachen Analyse häufig in einführenden Texten verwendet, kommen aber in der Praxis nur selten zum Einsatz. ⓘ

Bubble-Sortierung

Bubble Sort, ein Sortieralgorithmus, der eine Liste kontinuierlich durchläuft und die Elemente so lange austauscht, bis sie in der richtigen Reihenfolge erscheinen. ⓘ

Bubble Sort ist ein einfacher Sortieralgorithmus. Der Algorithmus beginnt am Anfang des Datensatzes. Er vergleicht die ersten beiden Elemente, und wenn das erste größer ist als das zweite, tauscht er sie aus. Er setzt dies für jedes Paar benachbarter Elemente bis zum Ende des Datensatzes fort. Dann beginnt er wieder mit den ersten beiden Elementen und wiederholt dies so lange, bis beim letzten Durchgang keine Vertauschungen mehr stattgefunden haben. Die durchschnittliche Zeit und die schlechteste Leistung dieses Algorithmus ist O(n²), so dass er selten zum Sortieren großer, ungeordneter Datensätze verwendet wird. Bubble Sort kann zum Sortieren einer kleinen Anzahl von Elementen verwendet werden (wobei die asymptotische Ineffizienz keinen hohen Nachteil darstellt). Die Blasensortierung kann auch effizient für eine Liste beliebiger Länge verwendet werden, die nahezu sortiert ist (d. h. die Elemente sind nicht signifikant verschoben). Wenn beispielsweise eine beliebige Anzahl von Elementen nur um eine Position verschoben ist (z. B. 0123546789 und 1032547698), werden sie durch den Austausch von Bubble Sort im ersten Durchgang in die richtige Reihenfolge gebracht, im zweiten Durchgang werden alle Elemente in der richtigen Reihenfolge gefunden, so dass die Sortierung nur 2n Zeit benötigt. ⓘ

Kamm-Sortierung

Kamm-Sortierung ist ein relativ einfacher Sortieralgorithmus, der auf der Bubble-Sortierung basiert und ursprünglich von Włodzimierz Dobosiewicz im Jahr 1980 entwickelt wurde. Später wurde er von Stephen Lacey und Richard Box in einem im April 1991 im Byte Magazine veröffentlichten Artikel wiederentdeckt und popularisiert. Die Grundidee besteht darin, Schildkröten oder kleine Werte in der Nähe des Listenendes zu eliminieren, da diese bei einer Blasensortierung die Sortierung enorm verlangsamen. (Rabbits, große Werte am Anfang der Liste, stellen bei der Bubble-Sortierung kein Problem dar.) Dies wird dadurch erreicht, dass zunächst Elemente, die einen bestimmten Abstand zueinander haben, in der Anordnung vertauscht werden, anstatt nur Elemente zu vertauschen, wenn sie nebeneinander liegen, und dann der gewählte Abstand verkleinert wird, bis es wie eine normale Bubble-Sortierung funktioniert. Wenn Shellsort also als eine verallgemeinerte Version der Einfügesortierung angesehen werden kann, bei der Elemente in einem bestimmten Abstand zueinander vertauscht werden, so kann die Kamm-Sortierung als die gleiche Verallgemeinerung der Bubble-Sortierung angesehen werden. ⓘ

Austausch-Sortierung

Exchange Sort wird manchmal mit Bubble Sort verwechselt, obwohl die Algorithmen in der Tat unterschiedlich sind. Bei der Austauschsortierung wird das erste Element mit allen darüber liegenden Elementen verglichen und gegebenenfalls vertauscht, um zu gewährleisten, dass das erste Element in der endgültigen Sortierreihenfolge korrekt ist; anschließend wird dasselbe für das zweite Element getan usw. Es fehlt der Vorteil der Bubble-Sortierung, in einem Durchgang zu erkennen, ob die Liste bereits sortiert ist, aber es kann im schlimmsten Fall um einen konstanten Faktor schneller sein als die Bubble-Sortierung (ein Durchgang weniger über die zu sortierenden Daten; halb so viele Vergleiche insgesamt). Wie jede einfache O(n²)-Sortierung kann sie bei sehr kleinen Datenmengen recht schnell sein, obwohl die Einfügesortierung im Allgemeinen schneller ist. ⓘ

Verteilungssortierungen

Distributionssortierung bezieht sich auf jeden Sortieralgorithmus, bei dem die Daten von der Eingabe auf mehrere Zwischenstrukturen verteilt werden, die dann gesammelt und an der Ausgabe platziert werden. Zum Beispiel sind sowohl Bucket Sort als auch Flashsort verteilungsbasierte Sortieralgorithmen. Verteilungssortieralgorithmen können auf einem einzigen Prozessor verwendet werden, oder sie können ein verteilter Algorithmus sein, bei dem einzelne Teilmengen separat auf verschiedenen Prozessoren sortiert und dann kombiniert werden. Dies ermöglicht das externe Sortieren von Daten, die zu groß sind, um in den Speicher eines einzelnen Computers zu passen. ⓘ

Zählende Sortierung

Zählsortierung ist anwendbar, wenn bekannt ist, dass jede Eingabe zu einer bestimmten Menge (S) von Möglichkeiten gehört. Der Algorithmus läuft in O(|S| + n) Zeit und O(|S|) Speicher, wobei n die Länge der Eingabe ist. Es wird ein ganzzahliges Array der Größe |S| erstellt und das i-te Bin verwendet, um das Auftreten des i-ten Mitglieds von S in der Eingabe zu zählen. Jede Eingabe wird dann gezählt, indem der Wert des entsprechenden bin inkrementiert wird. Anschließend wird das Zählfeld in einer Schleife durchlaufen, um alle Eingaben in der richtigen Reihenfolge anzuordnen. Dieser Sortieralgorithmus kann oft nicht verwendet werden, da S ziemlich klein sein muss, damit der Algorithmus effizient ist, aber er ist extrem schnell und zeigt ein großartiges asymptotisches Verhalten, wenn n zunimmt. Er kann auch modifiziert werden, um ein stabiles Verhalten zu erreichen. ⓘ

Eimersortierung

Bucket Sort ist ein Divide-and-Conquer-Sortieralgorithmus, der die Zählsortierung verallgemeinert, indem er ein Array in eine endliche Anzahl von Buckets partitioniert. Jeder Bucket wird dann einzeln sortiert, entweder mit einem anderen Sortieralgorithmus oder durch rekursive Anwendung des Bucket-Sortieralgorithmus. ⓘ

Eine Bucket-Sortierung funktioniert am besten, wenn die Elemente des Datensatzes gleichmäßig über alle Buckets verteilt sind. ⓘ

Radix-Sortierung

Radix-Sortierung ist ein Algorithmus, der Zahlen durch Verarbeitung einzelner Ziffern sortiert. n Zahlen, die jeweils aus k Ziffern bestehen, werden in O(n - k) Zeit sortiert. Radix sort kann die Ziffern jeder Zahl entweder ab der niedrigstwertigen Ziffer (LSD) oder ab der höchstwertigen Ziffer (MSD) verarbeiten. Der LSD-Algorithmus sortiert die Liste zunächst nach der niedrigstwertigen Ziffer, wobei die relative Reihenfolge der Ziffern durch eine stabile Sortierung beibehalten wird. Dann werden sie nach der nächsten Ziffer sortiert, und so weiter von der niedrigstwertigen bis zur höchstwertigen, so dass am Ende eine sortierte Liste vorliegt. Während die LSD-Radixsortierung die Verwendung einer stabilen Sortierung erfordert, ist dies beim MSD-Radixsortierungsalgorithmus nicht der Fall (es sei denn, eine stabile Sortierung ist gewünscht). Die MSD-Radixsortierung an Ort und Stelle ist nicht stabil. Es ist üblich, dass der Zählsortieralgorithmus intern von der Radixsortierung verwendet wird. Ein hybrider Sortieransatz, wie z. B. die Verwendung von Insertion Sort für kleine Bins, verbessert die Leistung der Radix-Sortierung erheblich. ⓘ

Speichernutzungsmuster und Indexsortierung

Wenn sich die Größe des zu sortierenden Arrays dem verfügbaren Primärspeicher nähert oder diesen übersteigt, so dass (viel langsamerer) Festplatten- oder Swap-Speicher verwendet werden muss, wird das Speichernutzungsmuster eines Sortieralgorithmus wichtig, und ein Algorithmus, der ziemlich effizient war, als das Array noch problemlos in den Arbeitsspeicher passte, kann unpraktisch werden. In diesem Szenario wird die Gesamtzahl der Vergleiche (relativ) weniger wichtig, und die Anzahl der Speicherabschnitte, die auf die Festplatte kopiert oder von dort ausgelagert werden müssen, kann die Leistungsmerkmale eines Algorithmus dominieren. So können die Anzahl der Durchläufe und die Lokalisierung der Vergleiche wichtiger sein als die bloße Anzahl der Vergleiche, da Vergleiche nahe beieinander liegender Elemente mit der Geschwindigkeit des Systembusses (oder, mit Caching, sogar mit CPU-Geschwindigkeit) erfolgen, was im Vergleich zur Festplattengeschwindigkeit praktisch augenblicklich ist. ⓘ

Der weit verbreitete rekursive Quicksort-Algorithmus beispielsweise bietet bei ausreichendem Arbeitsspeicher eine recht vernünftige Leistung, ist aber aufgrund der rekursiven Art und Weise, in der er Teile des Arrays kopiert, weit weniger praktisch, wenn das Array nicht in den Arbeitsspeicher passt, da er eine Reihe von langsamen Kopier- oder Verschiebevorgängen von und zur Festplatte verursachen kann. In diesem Fall kann ein anderer Algorithmus vorzuziehen sein, auch wenn er mehr Vergleiche erfordert. ⓘ

Eine Möglichkeit, dieses Problem zu umgehen, die gut funktioniert, wenn komplexe Datensätze (wie in einer relationalen Datenbank) nach einem relativ kleinen Schlüsselfeld sortiert werden, besteht darin, einen Index in das Array zu erstellen und dann den Index zu sortieren, anstatt das gesamte Array. (Eine sortierte Version des gesamten Arrays kann dann in einem Durchgang erzeugt werden, indem aus dem Index gelesen wird, aber selbst das ist oft unnötig, da der sortierte Index ausreicht.) Da der Index viel kleiner ist als das gesamte Array, kann er leicht in den Speicher passen, wo das gesamte Array nicht passen würde, wodurch das Problem der Plattenauslagerung effektiv beseitigt wird. Dieses Verfahren wird manchmal als "Tag-Sortierung" bezeichnet. ⓘ

Eine andere Technik zur Überwindung des Speicherplatzproblems ist die externe Sortierung. Eine der Möglichkeiten besteht darin, zwei Algorithmen so zu kombinieren, dass die Stärken der beiden Algorithmen genutzt werden, um die Gesamtleistung zu verbessern. Zum Beispiel könnte das Array in Chunks unterteilt werden, die so groß sind, dass sie in den RAM passen, der Inhalt jedes Chunks wird mit einem effizienten Algorithmus (z. B. Quicksort) sortiert, und die Ergebnisse werden mit einem k-way merge zusammengeführt, ähnlich wie bei Merge Sort. Dies ist schneller als die Durchführung von Merge Sort oder Quicksort über die gesamte Liste. ⓘ

Die Techniken können auch kombiniert werden. Für die Sortierung sehr großer Datenmengen, die den Systemspeicher bei weitem übersteigen, muss möglicherweise sogar der Index mit einem Algorithmus oder einer Kombination von Algorithmen sortiert werden, der/die so konzipiert ist, dass er/sie mit virtuellem Speicher vernünftig arbeiten kann, d. h., dass weniger Auslagerungen erforderlich sind. ⓘ

In den Fällen, bei denen das Umstellen der Daten mit hohem Aufwand verbunden ist, kann man auch indirektes Sortieren anwenden. Man benötigt dazu zusätzlichen Speicher proportional zur Anzahl der Elemente (bspw. einen Zeiger auf das jeweilige Element, oder dessen Indexnummer im Basis-Array). Dann wird dieses Array sortiert und stellt somit einen (gemäß dem Vergleichskriterium) sortierten Index dar. Sollen die eigentlichen Daten anschließend ebenfalls in die richtige Reihenfolge gebracht werden, ist ein zusätzlicher Aufwand von $\Theta \left(n\right)$ erforderlich. ⓘ

Ist auch der (wahlfreie) Zugriff auf die Elemente „teuer“, so werden mitunter auch diejenigen Datenkomponenten in den Index übernommen, die in den Sortierschlüssel einfließen/der Sortierschlüssel sind. Dies benötigt dann weiteren zusätzlichen Speicherplatz. ⓘ

Verwandte Algorithmen

Zu den verwandten Problemen gehören die ungefähre Sortierung (Sortieren einer Folge bis zu einem gewissen Grad der richtigen Reihenfolge), die partielle Sortierung (Sortieren nur der k kleinsten Elemente einer Liste oder Auffinden der k kleinsten Elemente, aber ungeordnet) und die Auswahl (Berechnen des k-ten kleinsten Elements). Diese Aufgaben können ineffizient durch eine Gesamtsortierung gelöst werden, aber es gibt effizientere Algorithmen, die oft durch Verallgemeinerung eines Sortieralgorithmus abgeleitet werden. Das bekannteste Beispiel ist quickselect, das mit quicksort verwandt ist. Umgekehrt lassen sich einige Sortieralgorithmen durch die wiederholte Anwendung eines Auswahlalgorithmus ableiten; quicksort und quickselect können als derselbe Schwenkzug betrachtet werden, der sich nur darin unterscheidet, ob man auf beiden Seiten (quicksort, divide-and-conquer) oder auf einer Seite (quickselect, decrease-and-conquer) rekursiert. ⓘ

Eine Art Gegenstück zu einem Sortieralgorithmus ist ein Mischer-Algorithmus. Diese unterscheiden sich grundlegend, da sie eine Quelle für Zufallszahlen benötigen. Mischen kann auch durch einen Sortieralgorithmus implementiert werden, nämlich durch eine zufällige Sortierung: jedem Element der Liste wird eine Zufallszahl zugewiesen, und dann wird auf der Grundlage der Zufallszahlen sortiert. In der Praxis wird dies jedoch in der Regel nicht gemacht, und es gibt einen bekannten einfachen und effizienten Algorithmus für das Mischen: den Fisher-Yates-Shuffle. ⓘ

Sortieralgorithmen sind in vielen Situationen untauglich, um eine Reihenfolge zu finden. In der Regel dann, wenn Elemente keine verlässliche Vergleichsfunktion haben (Crowdsourced-Präferenzen wie Abstimmungssysteme), Vergleiche sehr kostspielig sind (Sport) oder wenn es unmöglich wäre, alle Elemente für alle Kriterien paarweise zu vergleichen (Suchmaschinen). In diesen Fällen wird das Problem in der Regel als Ranking bezeichnet, und das Ziel besteht darin, das "beste" Ergebnis für einige Kriterien anhand von Wahrscheinlichkeiten zu finden, die aus Vergleichen oder Rankings abgeleitet werden. Ein gängiges Beispiel ist das Schachspiel, bei dem die Spieler mit dem Elo-Rating-System eingestuft werden und die Rangfolge durch ein Turniersystem anstelle eines Sortieralgorithmus bestimmt wird. ⓘ

Sortierung nach Beziehungen

Wenn nicht mehr nach Eigenschaften, sondern nur noch nach paarweisen Beziehungen sortiert werden kann, so spricht man von einer topologischen Sortierung. Dies ist beispielsweise der Fall, wenn Aufgaben erledigt werden müssen, manche Aufgaben aber unbedingt vor anderen durchzuführen sind, bei anderen jedoch die Reihenfolge keine Rolle spielt. ⓘ

Für das topologische Sortieren gibt es Algorithmen, deren Laufzeit von der Anzahl der Beziehungen abhängt. Topologisches Sortieren ist nicht möglich, wenn gegenseitige (zyklische) Abhängigkeiten bestehen. Eine topologische Sortierung muss nicht eindeutig sein. ⓘ

Wenn die Beziehungen vollständig sind, also für je zwei Objekte eine Abhängigkeit vorgegeben ist, so geht die topologische Sortierung in eine gewöhnliche Sortierung über. ⓘ

Beweis der unteren Schranke für vergleichsbasiertes Sortieren

Es lässt sich beweisen, dass ein vergleichsbasiertes Sortierverfahren nicht schneller als $\Omega (n\cdot \log(n))$ sein kann: Sei $B$ der Entscheidungsbaum für die Zahlenfolge $X=(x_{1},\ldots ,x_{n})$. Da alle Permutationen von $X$ das Ergebnis des Sortieralgorithmus sein könnten, muss der Entscheidungsbaum $B$ mindestens $n!$ Blätter haben. Da eine Mindestanzahl von Schritten gesucht ist, treten im Entscheidungsbaum keine unnötigen Vergleiche auf. ⓘ

In einem Entscheidungsbaum mit $n!$ Blättern beträgt die maximale und die mittlere Tiefe eines Blattes mindestens $\log(n!)$. Da eine untere Schranke gesucht ist, kann $n!$ mittels $n!\geq \left({\frac {n}{2}}\right)^{n/2}$ nach unten hin abgeschätzt werden. Damit gilt $\log(n!)\geq \left({\frac {n}{2}}\right)\cdot \log \left({\frac {n}{2}}\right)=\Omega (n\cdot \log(n))$. ⓘ

Es bleibt noch zu zeigen, dass in einem Binärbaum mit $k$ Blättern die maximale und die mittlere Tiefe eines Blattes mindestens $\log(k)$ beträgt. Angenommen $B$ sei ein Binärbaum, für welchen die obige Aussage nicht gilt. Seien $T_{1}$ und $T_{2}$ Teilbäume eines Binärbaumes mit $k>2$ Blättern. Für die Anzahl der Blätter $k_{1}$ in $T_{1}$ bzw. $k_{2}$ in $T_{2}$ gilt nun offensichtlich $k_{1}<k$, $k_{2}<k$ und $k_{1}+k_{2}=k$. Für die Tiefe jedes Blattes, bezogen auf die Wurzel von $B$, gilt:

${\begin{aligned}{\text{mittlere Tiefe}}(B)&={\frac {k_{1}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{1})+1)+{\frac {k_{2}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{2})+1)\\&\geq {\frac {k_{1}}{k}}\cdot (\log(k_{1})+1)+{\frac {k_{2}}{k}}\cdot (\log(k_{2})+1)\\&={\frac {1}{k}}\cdot (k_{1}\cdot \log(2\cdot k_{1})+k_{2}\cdot \log(2\cdot k_{2}))\end{aligned}}$ ⓘ

Das Minimum dieser Funktion liegt nun bei $k_{1}+k_{2}=k$ und $k_{1}=k_{2}={\frac {k}{2}}$. Eingesetzt in obige Formel ergibt das:

${\text{mittlere Tiefe}}(B)\geq {\frac {1}{k}}\cdot \left({\frac {k}{2}}\cdot \log(k)+{\frac {k}{2}}\cdot \log(k)\right)=\log(k)$. ⓘ

Dies ergibt einen Widerspruch zur Annahme, womit obige Aussage bewiesen ist. ⓘ