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 23 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 23.
Indices 0 to 11, depth 0. The seed picks index 11, holding 12, as the pivot.
Pivot 12 chosen at random from 0 to 11.
1 is at most 12: it belongs on the left, so it moves to index 0.
1 moves to index 0.
2 is at most 12: it belongs on the left, so it moves to index 1.
2 moves to index 1.
3 is at most 12: it belongs on the left, so it moves to index 2.
3 moves to index 2.
4 is at most 12: it belongs on the left, so it moves to index 3.
4 moves to index 3.
5 is at most 12: it belongs on the left, so it moves to index 4.
5 moves to index 4.
6 is at most 12: it belongs on the left, so it moves to index 5.
6 moves to index 5.
7 is at most 12: it belongs on the left, so it moves to index 6.
7 moves to index 6.
8 is at most 12: it belongs on the left, so it moves to index 7.
8 moves to index 7.
9 is at most 12: it belongs on the left, so it moves to index 8.
9 moves to index 8.
10 is at most 12: it belongs on the left, so it moves to index 9.
10 moves to index 9.
11 is at most 12: it belongs on the left, so it moves to index 10.
11 moves to index 10.
The pivot 12 lands at index 11: 11 on its left, 0 on its right. A lopsided split, which a random pivot cannot rule out, only make rare.
12 placed at index 11.
Indices 0 to 10, 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 0 to 10.
1 is at most 10: it belongs on the left, so it moves to index 0.
1 moves to index 0.
2 is at most 10: it belongs on the left, so it moves to index 1.
2 moves to index 1.
3 is at most 10: it belongs on the left, so it moves to index 2.
3 moves to index 2.
4 is at most 10: it belongs on the left, so it moves to index 3.
4 moves to index 3.
5 is at most 10: it belongs on the left, so it moves to index 4.
5 moves to index 4.
6 is at most 10: it belongs on the left, so it moves to index 5.
6 moves to index 5.
7 is at most 10: it belongs on the left, so it moves to index 6.
7 moves to index 6.
8 is at most 10: it belongs on the left, so it moves to index 7.
8 moves to index 7.
9 is at most 10: it belongs on the left, so it moves to index 8.
9 moves to index 8.
11 is above 10: leave it.
11 stays.
The pivot 10 lands at index 9: 9 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.
10 placed at index 9.
Indices 0 to 8, depth 2. The seed picks index 6, holding 7, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 7 chosen at random from 0 to 8.
1 is at most 7: it belongs on the left, so it moves to index 0.
1 moves to index 0.
2 is at most 7: it belongs on the left, so it moves to index 1.
2 moves to index 1.
3 is at most 7: it belongs on the left, so it moves to index 2.
3 moves to index 2.
4 is at most 7: it belongs on the left, so it moves to index 3.
4 moves to index 3.
5 is at most 7: it belongs on the left, so it moves to index 4.
5 moves to index 4.
6 is at most 7: it belongs on the left, so it moves to index 5.
6 moves to index 5.
9 is above 7: leave it.
9 stays.
8 is above 7: leave it.
8 stays.
The pivot 7 lands at index 6: 6 on its left, 2 on its right. A reasonable split, which is what random pivots deliver most of the time.
7 placed at index 6.
Indices 0 to 5, 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 5.
1 is at most 2: it belongs on the left, so it moves to index 0.
1 moves to index 0.
6 is above 2: leave it.
6 stays.
3 is above 2: leave it.
3 stays.
4 is above 2: leave it.
4 stays.
5 is above 2: leave it.
5 stays.
The pivot 2 lands at index 1: 1 on its left, 4 on its right. A reasonable split, which is what random pivots deliver most of the time.
2 placed at index 1.
Indices 2 to 5, depth 4. The seed picks index 2, holding 3, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 3 chosen at random from 2 to 5.
6 is above 3: leave it.
6 stays.
4 is above 3: leave it.
4 stays.
5 is above 3: leave it.
5 stays.
The pivot 3 lands at index 2: 0 on its left, 3 on its right. A lopsided split, which a random pivot cannot rule out, only make rare.
3 placed at index 2.
Indices 3 to 5, depth 5. The seed picks index 4, holding 5, as the pivot, and it is swapped to the end so the ordinary partition can run.
Pivot 5 chosen at random from 3 to 5.
4 is at most 5: it belongs on the left, so it moves to index 3.
4 moves to index 3.
6 is above 5: leave it.
6 stays.
The pivot 5 lands at index 4: 1 on its left, 1 on its right. A reasonable split, which is what random pivots deliver most of the time.
5 placed at index 4.
Indices 7 to 8, depth 3. 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 7 to 8.
9 is above 8: leave it.
9 stays.
The pivot 8 lands at index 7: 0 on its left, 1 on its right. A lopsided split, which a random pivot cannot rule out, only make rare.
8 placed at index 7.
Sorted with 40 comparisons and 13 swaps, recursing 6 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 7, averaging 5.4. 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 40 comparisons. Depth 6 against 11 deterministic.