Es gibt übrigens einen viel zu wenig bekannten Sortieralgorithmus, dessen Laufzeit O (N) ist, also lediglich linear statt wie die meisten üblichen Algorithmen proportional zu N ⋅ log2 N mit der Anzahl N der sortierten Elemente wächst, ohne dabei die Einschränkungen eines Radixsort zu haben. Außerdem benötigt er nur eine lineare Anzahl von Vergleichen und keinen zusätzlichen Speicher, da er sich (im Gegensatz etwa zum heute allgegenwärtigen Mergesort und seinen Abkömmlingen) bequem in-place implementieren lässt. Natürlich bereitet es keinerlei Probleme, den Algoritmus in gleicher Weise auf verkettete Listen wie auf Arrays anzuwenden, denn es muss für die Vergleichsoperationen jeweils nur auf das vorhergehende Element zugegriffen werden.
Darüber hinaus ist der Algorithmus verblüffend einfach und auch außerhalb der Informationstechnik unter totalitären Diktatoren und ihren überzeugten Anhängern sehr beliebt.
Es handelt sich um Stalinsort. Einfach in einer Säuberung alle Elemente der Reihe nach durchgehen und dabei jedes Element erschieß… ähm… entfernen, das die (nicht vorhandene) sortierte Reihenfolge stört. Sicherlich, dabei geht viel verloren, aber dafür wird die angestrebte, erfreuliche Ordnung mit sehr geringem Aufwand hergestellt, und wo gehobelt wird, da fallen eben Späne. 👿
Quelle des Stalin-Fotos: Wikimedia Commons. Das Foto ist gemeinfrei.
