Loading...
Quick Sort picks a pivot and partitions the array so smaller values go left and larger go right, then recurses into each partition. Its average O(n log n) with small constants makes it the fastest general-purpose in-memory sort in practice; worst case is O(n²) with poor pivots, mitigated by randomized or median-of-three pivots.
Partitions around a pivot, then recurses on each side.
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n²) |
| Space | O(log n) |
| Stable | No |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
return arr
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1Sorting [5, 1, 4, 2] step by step:
The control flow of the algorithm as a diagram: