IntroSort
Quick sort that switches to heap sort when recursion gets too deep and to insertion sort on small ranges.
Decision · step 2 of 77More Sorts: Sorted input burns the budget, heap sort rescues
Indices 0 to 10, 11 values, depth budget 6. Big enough and budget left: partition it and recurse on both sides.
What you will see
A depth gauge; when it hits the limit the range is heap-sorted instead.
Cost
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(log n) |
Properties
- ✓ comparison based
- × stable
- ✓ in place
- × adaptive
- × online
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, compare two runs.
Screen readers: Cells announce index, value and state (comparing, swapped, sorted); each step announces the comparison outcome and any move.
Reduced motion: Swaps become value crossfades with outline flashes; sorted-region growth is a static span change.
Before this
Related
Taught by the same lesson
More Sorts covers these too, in the same run.