Sortierstabilität: was sie garantiert und wann sie wichtig ist

Worum es geht

Eine Sortierung ist stabil, wenn Elemente, die als gleich verglichen werden, ihre relative Eingabereihenfolge beibehalten. Das Sorting-HOWTO von Python hält fest, dass seine Sortierungen garantiert stabil sind. MDN weist darauf hin, dass die Spezifikation seit ECMAScript 2019 verlangt, dass Array.prototype.sort stabil ist. Das sort-Paket von Go dokumentiert Stable als Funktion, die die ursprüngliche Reihenfolge gleicher Elemente beibehält, getrennt von Sort, dessen Stabilität nicht garantiert ist. GNU sort besitzt --stable, was den letzten Vergleich über die gesamte Zeile deaktiviert. Stabilität ist eine Eigenschaft des Algorithmus: Merge Sort, Insertion Sort und Timsort sind stabil; ein einfacher Quicksort oder Heapsort ist es nicht.

Warum es wichtig ist

Dank Stabilität lassen sich Sortierungen miteinander kombinieren. Wer nach Datum und dann stabil nach Status sortiert, erhält Zeilen, die nach Status gruppiert sind, wobei die Daten innerhalb jeder Gruppe geordnet bleiben. Eine sortierbare Tabelle, die bei jedem Klick neu sortiert, behält die vorherige Reihenfolge bei Gleichstand bei, statt sie durcheinanderzubringen. Der Gegenfall ist SQL: ORDER BY auf einer nicht eindeutigen Spalte verspricht nichts über Gleichstände, sodass paginierte Ergebnisse eine Zeile zweimal oder gar nicht zeigen können, sofern keine eindeutige Tiebreaker-Spalte ergänzt wird.

So wird es angewendet

• Bei Mehrschlüssel-Sortierungen einen zusammengesetzten Schlüssel bevorzugen (key=lambda r: (r.status, r.date)): ein Durchlauf, und die Absicht ist sichtbar. Aufeinanderfolgende stabile Sortierungen vom unwichtigsten zum wichtigsten Schlüssel sind die Alternative, wenn Schlüssel unterschiedliche Richtungen benötigen.
• In SQL jede für Paginierung genutzte ORDER BY-Klausel mit einer eindeutigen Spalte abschliessen (ORDER BY created_at, id).
• Sich nur dort auf Stabilität verlassen, wo die Dokumentation sie festhält; das Wort in der Bibliotheksreferenz suchen, bevor man sich darauf verlässt.
• Pythons reverse=True behält gleiche Elemente in ihrer ursprünglichen Reihenfolge bei, was sich vom Sortieren und anschliessenden Umkehren der Liste unterscheidet.
• Auf der Kommandozeile -s bei GNU sort ergänzen, wenn Gleichstände die Dateireihenfolge behalten müssen, etwa beim Sortieren eines Logs nach einem Feld.

Stolpersteine

Tests, die sortierte Ausgaben mit Gleichständen vergleichen, hängen sowohl von der Stabilität als auch von der Eingabereihenfolge ab; die erwarteten Daten gleichstandsfrei gestalten oder mit einem vollständigen Schlüssel sortieren. Die Locale-Kollation (LC_ALL) ändert die Reihenfolge derselben Eingabe zwischen Maschinen, daher die Locale in Skripten fixieren. Stabile Algorithmen benötigen unter Umständen zusätzlichen Speicher (Merge-Puffer), was bei sehr grossen Arrays im Arbeitsspeicher relevant ist. Stabilität sagt nichts darüber aus, ob die Vergleichsfunktion konsistent ist: Ein inkonsistenter Komparator erzeugt in jedem Algorithmus eine undefinierte Reihenfolge.