Quicksort is a divide-and-conquer sort that picks a pivot, partitions elements into those smaller and larger than it, then recursively sorts each side. Average O(n log n), worst case O(n²).
Partitioning places the pivot in its final sorted position; everything left is smaller, everything right is larger. Recurse on both sides.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(In-place partitioning is used in practice to save memory.)
| Case | Time | Cause |
|---|---|---|
| Best/Average | O(n log n) | balanced partitions |
| Worst | O(n²) | already-sorted with bad pivot |
In-place quicksort uses O(log n) stack space.
Usually the fastest in practice due to cache friendliness and low overhead, and it is in-place. The O(n²) worst case is avoided with a randomized or median-of-three pivot. It is not stable.
Quicksort is the default in many standard libraries because of its excellent average-case speed and low memory use.
Understanding why pivot choice causes the O(n²) worst case teaches a key lesson: average and worst case can diverge sharply.
It is a favorite interview topic precisely because of that nuance.