Visualizer › Sorting
Quick Sort
Picks a pivot, partitions the array so smaller elements go left and bigger ones go right, then sorts both sides recursively.
How it works
- Usually the fastest in practice — in-place and cache friendly.
- Worst case O(n²) when the pivot is always the smallest or largest (e.g. sorted input with the last element as pivot).
- A random pivot makes the worst case very unlikely.
Complexity
- Best time: O(n log n)
- Average time: O(n log n)
- Worst time: O(n²)
- Extra space: O(log n)
- Stable: no
Code (Python)
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
pivot, i = a[hi], lo
for j in range(lo, hi):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i] # pivot in place
quick_sort(a, lo, i - 1)
quick_sort(a, i + 1, hi)
return aPractise: Arrays problems