Introsort

Introsort ist ein Sortieralgorithmus. Der Begriff ist eine Kurzform für „introspektives Sortieren“. Der Algorithmus ist eine Variation von Quicksort, welche in entarteten Fällen auf ein anderes Sortierverfahren mit Worst-Case-Laufzeit $\mathcal{O}(n \log n)$ (zum Beispiel Heapsort) zurückfällt. Dazu wird zu Beginn jedes Rekursionsschrittes anhand einer Bewertungsfunktion entschieden, ob ein anderer Algorithmus für die Sortierung der Teilliste verwendet werden soll (zum Beispiel bei Erreichen einer bestimmten Rekursionstiefe).

Auf diese Weise wird die Geschwindigkeit von Quicksort mit einer Worst-Case-Zeitkomplexität von $\mathcal{O}(n \log n)$ – gegenüber $\mathcal{O}(n^2)$ bei reinem Quicksort – gekoppelt.

Bekannt geworden ist Introsort vor allem dadurch, dass Silicon Graphics in seiner Standard Template Library für C++ seit einigen Jahren auf Introsort statt Quicksort zurückgreift. Inzwischen wurde Introsort auch in andere Implementierungen der C++ Standard Library übernommen, unter anderem in die der GCC. Derzeit gilt Introsort als schnellstes instabiles Sortierverfahren.

Literatur

• David R. Musser: Introspective Sorting and Selection Algorithms. Software Practice and Experience 27(8):983, 1997

Weblinks

• http://www.sgi.com/tech/stl/sort.html Introsort in der STL von SGI
• "Implementierung und Untersuchung des introspektiven Sortieralgorithmus Introsort" Studienarbeit an der BA Stuttgart von Ralph Unden