A
AiTechWorlds
AiTechWorlds
See Introsort run Quick Sort then fall back to Heap Sort at the depth limit — the algorithm behind C++ std::sort.
def introsort(a, lo, hi, depth):
if hi - lo < 16:
insertion_sort(a, lo, hi); return
if depth == 0:
heap_sort_range(a, lo, hi); return
p = partition(a, lo, hi)
introsort(a, lo, p - 1, depth - 1)
introsort(a, p + 1, hi, depth - 1)Introsort begins with Quick Sort and switches to Heap Sort once recursion depth exceeds a limit, combining Quick Sort speed with a guaranteed O(n log n) worst case.
| Best | O(n log n) |
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(log n) |
| Stable | No |
| In-place | Yes |
The Introsort Visualizer animates how Introspective Sort works: it starts with Quick Sort, but if the recursion depth exceeds a limit (about 2·log n), it switches that range to Heap Sort to avoid Quick Sort's O(n²) worst case. Introsort runs in O(n log n) in all cases, uses O(log n) stack space, and is not stable. It is the algorithm behind C++ std::sort.
Generate an array
Click New Array or adjust the size slider for a random dataset.
Play the animation
Press Play to watch partitioning, and the Heap Sort fallback when depth runs out.
Step and scrub
Step forward/back or drag the timeline to study the switch in strategy.
Read the synced code
The highlighted pseudocode line tracks recursion and the fallback; switch tabs for C++, Java, Python, or JavaScript.
100% Private — No Server Required
All processing happens directly in your browser. No data is uploaded, stored, or transmitted to any server.
Last reviewed on June 14, 2026 by the AiTechWorlds Tools Team. All processing runs locally in your browser.