Interactive demo
Introsort Visualization
Introsort, introduced by David Musser in 1997, starts as quicksort, but watches its recursion depth. If quicksort runs into a bad case, it switches to heapsort, so it never takes more than n log n steps. Many standard libraries use it, for example GCC's std::sort for C++.
Choose “Hard case for quicksort”: the median of 3 keeps splitting off small parts until the depth limit hands over to heapsort.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element
- Pivot · element being sorted in
- “lower” arrow · larger child
- “greater” arrow · compared child
- Final position
Runtime and properties
Best case
O(n log n)
Good pivots split every section in half, as with quicksort.
Average case
O(n log n)
On most inputs it simply is quicksort with a median-of-3 pivot.
Worst case
O(n log n)
Once the depth limit is reached, heapsort finishes the part in n log n.
Extra memory
O(log n)
Only the recursion stack, at most the depth limit deep.
Stable
No
Swaps of quicksort and heapsort can change the order of equal elements.
In-place
Yes
Every part of it sorts within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort this page | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Quicksort with a depth limit
Introsort partitions like quicksort, with the median of the first, middle and last element as pivot. Every level of recursion counts towards a depth limit, usually 2 · log₂ n.
2. Heapsort as a safety net
If a part reaches the depth limit, the pivots were bad, and quicksort might take n² steps. Introsort then sorts that part with heapsort, which always needs n log n steps.
3. Simplified here
So that all three algorithms show up on 11 elements, the depth limit here is log₂ n instead of 2 · log₂ n, and parts of up to 3 elements are sorted with insertion sort (usually up to 16).