Choose a pivot, place smaller values to its left and greater-or-equal values to its right, then recursively sort both sides. Partitioning puts the pivot in its final position.
A quick-sort simulator showing partitioning and the call stack
Play, step, or seek with the slider. Already sorted exposes the worst case for this rightmost-pivot implementation.
Partitioning with i and j
j scans unprocessed values; i marks the next position for a value smaller than the pivot. The green interval lo…i−1 holds smaller values, and the red interval i…j−1 holds greater-or-equal values. Finally, move the pivot to i between these groups.
Worst case
On sorted input, a rightmost pivot is always the largest value, leaving one recursive side almost unchanged. Depth grows to n and comparisons to n(n−1)/2. Practical implementations use strategies such as randomized pivots, median-of-three selection, or fallback algorithms.
Coding exercises: quickselect
After partitioning, the pivot is fixed at index i. If i equals k, it is the requested order statistic; otherwise, recurse only on the side containing k. This gives expected O(n) selection with suitable pivots. For ordinary sorting, prefer sort(); for a few largest values, consider heapq.nsmallest, heapq.nlargest.