Introsort, the sort behind C++'s std::sort. It is quicksort with two escape hatches. A range of 4 or fewer values goes to insertion sort, which beats everything at that size. And each recursive call spends one unit of a depth budget, 2 log2 n = 6 here. A range that arrives with the budget spent is handed to heap sort, because that many partitions without finishing means the pivots have been bad and quicksort is sliding towards O(n^2).
Introsort on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 with a depth budget of 6.
Indices 0 to 10, 11 values, depth budget 6. Big enough and budget left: partition it and recurse on both sides.
Range 0 to 10 at depth 6.
Partition indices 0 to 10 around the last value, 11. i marks where the next smaller value will go. Every value at most 11 is swapped there as the scan passes it.
Partition 0 to 10 around 11.
1 is at most 11: swap it into index 0 and move i to 1.
1 moves to index 0.
2 is at most 11: swap it into index 1 and move i to 2.
2 moves to index 1.
3 is at most 11: swap it into index 2 and move i to 3.
3 moves to index 2.
4 is at most 11: swap it into index 3 and move i to 4.
4 moves to index 3.
5 is at most 11: swap it into index 4 and move i to 5.
5 moves to index 4.
6 is at most 11: swap it into index 5 and move i to 6.
6 moves to index 5.
7 is at most 11: swap it into index 6 and move i to 7.
7 moves to index 6.
8 is at most 11: swap it into index 7 and move i to 8.
8 moves to index 7.
9 is at most 11: swap it into index 8 and move i to 9.
9 moves to index 8.
10 is at most 11: swap it into index 9 and move i to 10.
10 moves to index 9.
Swap the pivot into index 10, its final place: 10 values on its left, 0 on its right.
11 placed at index 10.
Indices 0 to 9, 10 values, depth budget 5. Big enough and budget left: partition it and recurse on both sides.
Range 0 to 9 at depth 5.
Partition indices 0 to 9 around the last value, 10. i marks where the next smaller value will go. Every value at most 10 is swapped there as the scan passes it.
Partition 0 to 9 around 10.
1 is at most 10: swap it into index 0 and move i to 1.
1 moves to index 0.
2 is at most 10: swap it into index 1 and move i to 2.
2 moves to index 1.
3 is at most 10: swap it into index 2 and move i to 3.
3 moves to index 2.
4 is at most 10: swap it into index 3 and move i to 4.
4 moves to index 3.
5 is at most 10: swap it into index 4 and move i to 5.
5 moves to index 4.
6 is at most 10: swap it into index 5 and move i to 6.
6 moves to index 5.
7 is at most 10: swap it into index 6 and move i to 7.
7 moves to index 6.
8 is at most 10: swap it into index 7 and move i to 8.
8 moves to index 7.
9 is at most 10: swap it into index 8 and move i to 9.
9 moves to index 8.
Swap the pivot into index 9, its final place: 9 values on its left, 0 on its right.
10 placed at index 9.
Indices 0 to 8, 9 values, depth budget 4. Big enough and budget left: partition it and recurse on both sides.
Range 0 to 8 at depth 4.
Partition indices 0 to 8 around the last value, 9. i marks where the next smaller value will go. Every value at most 9 is swapped there as the scan passes it.
Partition 0 to 8 around 9.
1 is at most 9: swap it into index 0 and move i to 1.
1 moves to index 0.
2 is at most 9: swap it into index 1 and move i to 2.
2 moves to index 1.
3 is at most 9: swap it into index 2 and move i to 3.
3 moves to index 2.
4 is at most 9: swap it into index 3 and move i to 4.
4 moves to index 3.
5 is at most 9: swap it into index 4 and move i to 5.
5 moves to index 4.
6 is at most 9: swap it into index 5 and move i to 6.
6 moves to index 5.
7 is at most 9: swap it into index 6 and move i to 7.
7 moves to index 6.
8 is at most 9: swap it into index 7 and move i to 8.
8 moves to index 7.
Swap the pivot into index 8, its final place: 8 values on its left, 0 on its right.
9 placed at index 8.
Indices 0 to 7, 8 values, depth budget 3. Big enough and budget left: partition it and recurse on both sides.
Range 0 to 7 at depth 3.
Partition indices 0 to 7 around the last value, 8. i marks where the next smaller value will go. Every value at most 8 is swapped there as the scan passes it.
Partition 0 to 7 around 8.
1 is at most 8: swap it into index 0 and move i to 1.
1 moves to index 0.
2 is at most 8: swap it into index 1 and move i to 2.
2 moves to index 1.
3 is at most 8: swap it into index 2 and move i to 3.
3 moves to index 2.
4 is at most 8: swap it into index 3 and move i to 4.
4 moves to index 3.
5 is at most 8: swap it into index 4 and move i to 5.
5 moves to index 4.
6 is at most 8: swap it into index 5 and move i to 6.
6 moves to index 5.
7 is at most 8: swap it into index 6 and move i to 7.
7 moves to index 6.
Swap the pivot into index 7, its final place: 7 values on its left, 0 on its right.
8 placed at index 7.
Indices 0 to 6, 7 values, depth budget 2. Big enough and budget left: partition it and recurse on both sides.
Range 0 to 6 at depth 2.
Partition indices 0 to 6 around the last value, 7. i marks where the next smaller value will go. Every value at most 7 is swapped there as the scan passes it.
Partition 0 to 6 around 7.
1 is at most 7: swap it into index 0 and move i to 1.
1 moves to index 0.
2 is at most 7: swap it into index 1 and move i to 2.
2 moves to index 1.
3 is at most 7: swap it into index 2 and move i to 3.
3 moves to index 2.
4 is at most 7: swap it into index 3 and move i to 4.
4 moves to index 3.
5 is at most 7: swap it into index 4 and move i to 5.
5 moves to index 4.
6 is at most 7: swap it into index 5 and move i to 6.
6 moves to index 5.
Swap the pivot into index 6, its final place: 6 values on its left, 0 on its right.
7 placed at index 6.
Indices 0 to 5, 6 values, depth budget 1. Big enough and budget left: partition it and recurse on both sides.
Range 0 to 5 at depth 1.
Partition indices 0 to 5 around the last value, 6. i marks where the next smaller value will go. Every value at most 6 is swapped there as the scan passes it.
Partition 0 to 5 around 6.
1 is at most 6: swap it into index 0 and move i to 1.
1 moves to index 0.
2 is at most 6: swap it into index 1 and move i to 2.
2 moves to index 1.
3 is at most 6: swap it into index 2 and move i to 3.
3 moves to index 2.
4 is at most 6: swap it into index 3 and move i to 4.
4 moves to index 3.
5 is at most 6: swap it into index 4 and move i to 5.
5 moves to index 4.
Swap the pivot into index 5, its final place: 5 values on its left, 0 on its right.
6 placed at index 5.
Indices 0 to 4, 5 values, depth budget 0. The budget is spent: 6 partitions have not finished this stretch, so the pivots are degrading. Heap sort finishes it in O(k log k) no matter what.
Range 0 to 4 at depth 0.
Heap sort takes over indices 0 to 4. Treat the range as a binary heap, the value at 0 as the root, and sift every internal node down so the largest value rises to the front.
Heap sort on 5 values.
Build the heap: 2 at index 1 is smaller than its child 5, so they swap and the sift continues from index 4.
Swap 2 and 5.
Build the heap: 1 at index 0 is smaller than its child 5, so they swap and the sift continues from index 1.
Swap 1 and 5.
Build the heap: 1 at index 1 is smaller than its child 4, so they swap and the sift continues from index 3.
Swap 1 and 4.
The root holds the largest remaining value, 5: swap it to index 4, the last unsorted slot, and shrink the heap by one.
5 moves to index 4.
Restore the heap: 2 at index 0 is smaller than its child 4, so they swap and the sift continues from index 1.
Swap 2 and 4.
The root holds the largest remaining value, 4: swap it to index 3, the last unsorted slot, and shrink the heap by one.
4 moves to index 3.
Restore the heap: 1 at index 0 is smaller than its child 3, so they swap and the sift continues from index 2.
Swap 1 and 3.
The root holds the largest remaining value, 3: swap it to index 2, the last unsorted slot, and shrink the heap by one.
3 moves to index 2.
Restore the heap: 1 at index 0 is smaller than its child 2, so they swap and the sift continues from index 1.
Swap 1 and 2.
The root holds the largest remaining value, 2: swap it to index 1, the last unsorted slot, and shrink the heap by one.
2 moves to index 1.
Sorted with 57 comparisons and 61 swaps: 6 partitions, 0 small ranges finished by insertion sort, and heap sort rescued 1 stretch where the budget ran out. Quicksort's speed on average, heap sort's O(n log n) guarantee in the worst case, insertion sort's low overhead on tiny ranges: that combination is why introsort is the library default.
Sorted after 57 comparisons and 61 swaps.