Sort Target
Algorithm
Speed
Normal ~12s · 38 ms/step
Introsort(1997)
▶ Try this Source
O(n log n) ✗ Stable ✓ In-place
🔧 How it works

Starts with Quicksort but monitors recursion depth; switches to Heapsort when depth exceeds 2⌊log₂ n⌋ to guarantee O(n log n) worst-case, and finishes sub-arrays smaller than a fixed threshold with Insertion sort.

🎯 Key property

Combines the practical speed of Quicksort, the worst-case safety of Heapsort, and the low overhead of Insertion sort for small inputs, the foundation of std::sort in most C++ standard libraries.

👁 Watch for
  • Compare (Quicksort phase) left-right partition scan testing each element against the pivot; cross-boundary swaps follow
  • Swap (Heapsort fallback) when the depth limit is hit, the pattern shifts to sift-down swaps moving elements downward through heap levels
  • IndexWrite (Insertion sort finish) once sub-arrays shrink below the threshold, leftward element shifts replace partitioning
🕰 History 🌳 Lineage ⚡ Optimization
UsesTail Recursion EliminationHybrid SwitchingAdaptive Pivot SelectionSortedness DetectionPartial Insertion Sort CutoffSorting Networks for Small ArraysEarly-Out HeuristicSentinels (Unguarded Insertion)
Initial State
This is the array before sorting. Follow Introsort step by step.
Recursion Tree
[0..31)51736248139151114101216211723192218202429253127302628
0 / 317 ops ( 0.0%) 0.0%
• © 2026 guitarrapc. All rights reserved.
Sorting is
a spectacle.
Algorithms at work, in a daily vertical feed. Watch, play, challenge — and go deeper when you're ready.
Loading 0%
An unhandled error has occurred. Reload 🗙