Quick Sort
Pick a pivot. Partition the array so smaller values are left of it and larger values are right of it. Recurse on each side.
Pivot, partition, recurse
- comparisons
- 0
- result
- —
- 0
def quick_sort(arr, lo=0, hi=None): - 1
if hi is None: hi = len(arr) - 1 - 2
if lo >= hi: return - 3
p = partition(arr, lo, hi) - 4
quick_sort(arr, lo, p - 1) - 5
quick_sort(arr, p + 1, hi) - 6
- 7
def partition(arr, lo, hi): - 8
pivot = arr[hi] - 9
i = lo - 1 - 10
for j in range(lo, hi): - 11
if arr[j] <= pivot: - 12
i += 1 - 13
arr[i], arr[j] = arr[j], arr[i] - 14
arr[i + 1], arr[hi] = arr[hi], arr[i + 1] - 15
return i + 1
What you just watched
Quicksort's magic is the partition step. Pick a pivot (here: the last element). Walk the rest of the range, swap anything smaller-or-equal toward the front. After one pass, everything left of the pivot is ≤ it and everything right is ≥ it. Recurse on the two sides.
Average case: O(n log n) with the smallest constants of any general-purpose sort — that's why it's the default in many language standard libraries.
The worst case is O(n²): when the pivot is always the smallest or largest, partitions become 0 / n−1 and recursion depth blows up. Try the Worst case button (a reversed array — pivot is the largest each time) and watch the comparison count grow much faster than usual. Real-world implementations randomize the pivot or use median-of-three to avoid this.