IntroSort

Introsort is the one that actually ships. When you call sort in C++, this is roughly what runs. It starts out as quick sort because quick sort is fast in practice, but it keeps an eye on how deep the recursion is going. If a bad run of pivots pushes it too deep, the point where plain quick sort would slump to n², it bails out and heap sorts that chunk instead, which guarantees n log n. And once a piece gets small enough, it stops recursing and finishes with insertion sort, which wins on tiny runs.

So it’s a hybrid of the three you’ve already seen: quick sort for everyday speed, heap sort as a safety net, insertion sort for the small stuff. The payoff is that you get quick sort’s speed with none of its worst case. Feed it the Sorted or Reversed inputs, the ones that wreck a plain last-pivot quick sort, and watch it cap the depth and hand the rest off to heap sort instead of blowing up.

Hit Play to watch it run, or use Next and Back to step one comparison at a time. Shuffle deals a fresh array, the violet band is the chunk it’s working on right now, and the highlighted line shows you where the code is at each step.