Quicksort, but the pivot is chosen at random from the range instead of always being the last value. With the last value as pivot, this exact input recurses 11 deep, the worst case, one level per value. A random pivot does not make any input impossible, it makes no input reliably bad: whoever wrote the input cannot know which value will be the pivot. Seed 7 decides the rolls here. Change it and the same input takes a different path.
Randomized quicksort on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 with seed 7.
Indices 0 to 11, depth 0. The seed picks index 7, holding 8, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 8 chosen at random from 0 to 11.
1 is at most 8: it belongs on the left, so it moves to index 0.
1 moves to index 0.
2 is at most 8: it belongs on the left, so it moves to index 1.
2 moves to index 1.
3 is at most 8: it belongs on the left, so it moves to index 2.
3 moves to index 2.
4 is at most 8: it belongs on the left, so it moves to index 3.
4 moves to index 3.
5 is at most 8: it belongs on the left, so it moves to index 4.
5 moves to index 4.
6 is at most 8: it belongs on the left, so it moves to index 5.
6 moves to index 5.
7 is at most 8: it belongs on the left, so it moves to index 6.
7 moves to index 6.
12 is above 8: leave it.
12 stays.
9 is above 8: leave it.
9 stays.
10 is above 8: leave it.
10 stays.
11 is above 8: leave it.
11 stays.
The pivot 8 lands at index 7: 7 on its left, 4 on its right. A reasonable split, which is what random pivots deliver most of the time.
8 placed at index 7.
Indices 0 to 6, depth 1. The seed picks index 5, holding 6, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 6 chosen at random from 0 to 6.
1 is at most 6: it belongs on the left, so it moves to index 0.
1 moves to index 0.
2 is at most 6: it belongs on the left, so it moves to index 1.
2 moves to index 1.
3 is at most 6: it belongs on the left, so it moves to index 2.
3 moves to index 2.
4 is at most 6: it belongs on the left, so it moves to index 3.
4 moves to index 3.
5 is at most 6: it belongs on the left, so it moves to index 4.
5 moves to index 4.
7 is above 6: leave it.
7 stays.
The pivot 6 lands at index 5: 5 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.
6 placed at index 5.
Indices 0 to 4, depth 2. The seed picks index 3, holding 4, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 4 chosen at random from 0 to 4.
1 is at most 4: it belongs on the left, so it moves to index 0.
1 moves to index 0.
2 is at most 4: it belongs on the left, so it moves to index 1.
2 moves to index 1.
3 is at most 4: it belongs on the left, so it moves to index 2.
3 moves to index 2.
5 is above 4: leave it.
5 stays.
The pivot 4 lands at index 3: 3 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.
4 placed at index 3.
Indices 0 to 2, depth 3. The seed picks index 1, holding 2, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 2 chosen at random from 0 to 2.
1 is at most 2: it belongs on the left, so it moves to index 0.
1 moves to index 0.
3 is above 2: leave it.
3 stays.
The pivot 2 lands at index 1: 1 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.
2 placed at index 1.
Indices 8 to 11, depth 1. The seed picks index 9, holding 10, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 10 chosen at random from 8 to 11.
9 is at most 10: it belongs on the left, so it moves to index 8.
9 moves to index 8.
12 is above 10: leave it.
12 stays.
11 is above 10: leave it.
11 stays.
The pivot 10 lands at index 9: 1 on its left, 2 on its right. A reasonable split, which is what random pivots deliver most of the time.
10 placed at index 9.
Indices 10 to 11, depth 2. The seed picks index 10, holding 11, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 11 chosen at random from 10 to 11.
12 is above 11: leave it.
12 stays.
The pivot 11 lands at index 10: 0 on its left, 1 on its right. A lopsided split, which a random pivot cannot rule out, only make rare.
11 placed at index 10.
Sorted with 27 comparisons and 12 swaps, recursing 4 deep. The last-value pivot needs 11 on this input. Run the same input under 30 other seeds and the depth ranges from 4 to 8, averaging 5.2. That average over the algorithm's own coin flips, for a fixed input, is the expected running time. It is not the same as averaging over inputs: here the input is as bad as it gets and the expectation is still O(n log n), because the only way to be slow is a run of unlucky rolls, and that run is rare on every input, not just on typical ones.
Sorted after 27 comparisons. Depth 4 against 11 deterministic.