Stephan Barth: Ein neuer Sortieralgorithmus und wieso wir einen weiteren brauchen

Es spricht Stephan Barth über:
Ein neuer Sortieralgorithmus und wieso wir einen weiteren brauchen

Abstract:
Sortieralgorithmen gelten gemeinhin als ein gelöstes Problem:
Sortieren in O(n log n) ist optimal mit bekannten und nicht zu
komplizierten Lösungen.

Dennoch gibt es für Sortieralgorithmen noch Verbesserungspotential:
Einige Sortieralgorithmen eignen sich für bestimmte Aufgaben besser
als andere, beispielsweise gibt es Timsort, eine Variante von
Mergesort, welche teilweise vorsortierte Listen für eine schnellere
Sortierung weiterverwenden kann; zudem partial Quicksort/Quickselect,
eine Variante von Quicksort, welche effizient das k-kleinste Element
finden kann, ohne die ganze Liste sortieren zu müssen.

Um einen Sortieralgorithmus zu erhalten, welcher in einer Reihe von
Spezialfällen Vorteile gegenüber anderen Sortieralgorithmen hat,
kombinieren wir Konzepte aus Quicksort, Mergesort, Bucketsort und
Heaps zu einem neuen Sortieralgorithmus: Platypussort.

Dadurch, dass Platypussort sich in vielen Anwedungsfällen besser
verhält, als verbreitete Algorithmen, aber dennoch die gleiche
worst-case-Laufzeit O(n log n) hat, hätte er Vorteile als
Standardsortieralgorithmus. Diese Vorteile erkauft er sich allerdings
nicht zuletzt durch einen deutlich höheren Implementierungsaufwand.