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 $\Omega (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 ${\textstyle {\mathcal {O}}(n\log n)}$ worst-case Zeitkomplexität gekoppelt (gegenüber ${\textstyle {\mathcal {O}}(n^{2})}$ bei reinem Quicksort). Die exakte Laufzeit ist in den entarteten Fällen etwas höher als bei direkter Anwendung des optimalen Algorithmus, da bis zum Rückfall auf das alternative Sortierverfahren Quicksort durchlaufen wird.

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.

Literatur

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

Weblinks

• Introsort in der Standard Template Library von Silicon Graphics International
• Implementierung und Untersuchung des introspektiven Sortieralgorithmus Introsort. Studienarbeit an der BA Stuttgart von Ralph Unden (PDF; 328 kB)