# Introsort visualised: quick sort with a heap fallback

> Interactive Introsort: Quick Sort that falls back to Heap Sort when recursion gets too deep and sorts small ranges with Insertion Sort. Guaranteed O(n log n).

Address: https://marckimmel.de/en/informatik/sortieralgorithmen/intro-sort
Deutsche Fassung: https://marckimmel.de/informatik/sortieralgorithmen/intro-sort.md

Quick Sort with a depth limit, falling back to Heap Sort on deep recursion.

Introsort (Introspective Sort) fixes the pathological worst case of Quick Sort, which can degrade to O(n²) for unfortunate pivots. It starts with regular Quick Sort but watches the recursion depth. Once depth exceeds 2 · ⌊log₂(n)⌋, the algorithm switches to Heap Sort, which guarantees O(n log n). Very small sub-arrays (typically ≤ 16 elements) are finished with Insertion Sort which is very fast on small inputs. This combines the average-case speed of Quick Sort, the worst-case O(n log n) guarantee of Heap Sort and the constant-factor advantage of Insertion Sort on small ranges. Memory is O(log n) for the recursion stack and the algorithm is not stable.

Standard sort algorithm in the C++ STL (std::sort) since C++11. First choice when a generic, fast in-place sort with guaranteed O(n log n) worst case is needed.

## Related

- [Sorting Algorithms](https://marckimmel.de/en/informatik/sortieralgorithmen.md)