Editing Introsort (section)

{{Short description|Hybrid sorting algorithm}}
{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|caption=
|data=[[Array data structure|Array]]
|time=O(''n'' log ''n'')
|average-time=O(''n'' log ''n'')
|space=
|optimal=yes
}}

'''Introsort''' or '''introspective sort''' is a [[hybrid algorithm|hybrid]] [[sorting algorithm]] that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with [[quicksort]], it switches to [[heapsort]] when the recursion depth exceeds a level based on (the [[logarithm]] of) the number of elements being sorted and it switches to [[insertion sort]] when the number of elements is below some threshold. This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case [[Big-O notation|O]](''n'' log ''n'') runtime due to the heap sort. Since the three algorithms it uses are [[comparison sort]]s, it is also a comparison sort.

Introsort was invented by [[David Musser]] in {{harvtxt|Musser|1997}}, in which he also introduced [[introselect]], a hybrid [[selection algorithm]] based on [[quickselect]] (a variant of quicksort), which falls back to [[median of medians]] and thus provides worst-case linear complexity, which is optimal. Both algorithms were introduced with the purpose of providing [[generic algorithm]]s for the [[C++ Standard Library]] which had both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.<ref>"[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]</ref>  Introsort is [[In-place_algorithm|in-place]] and a non-[[Sorting_algorithm#Stability|stable]] algorithm.