Introsort

Introsort is a sorting algorithm . The term is short for "introspective sorting". The algorithm is a variation of quicksort which, in degenerate cases, falls back on a different sorting method with worst-case runtime (for example heapsort ). For this purpose, at the beginning of each recursion step, an evaluation function is used to decide whether another algorithm should be used for sorting the partial list (for example when a certain recursion depth is reached). ${\displaystyle {\mathcal {O}}(n\log n)}$

In this way, the speed of Quicksort is coupled with a -Worst-Case time complexity (compared to pure Quicksort). In the degenerate cases, the exact running time is slightly higher than when the optimal algorithm is used directly, since Quicksort is run through until the alternative sorting method is used. ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle \Theta (n^{2})}$

Introsort is best known because Silicon Graphics has been using Introsort instead of Quicksort in its standard template library for C ++ for several years. In the meantime, Introsort has also been adopted in other implementations of the C ++ Standard Library, including those of the GCC . Introsort is currently considered the fastest unstable sorting process .

literature

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

Web links

• Introsort in the Standard Template Library from Silicon Graphics International
• Implementation and investigation of the introspective sorting algorithm Introsort. Student thesis at the BA Stuttgart by Ralph Unden (PDF; 328 kB)