SortingSorting

Quick Sort

Pick a pivot, partition elements into smaller and larger sides, and recursively sort each side.

Learn Quick Sort →
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/43Start with 8 elements. Quick sort picks a pivot, partitions the range around it, then recurses on both sides (Lomuto partition, last element as pivot).
PivotComparing with pivotSwappedLess than pivotIn final position
PseudocodeLearn Quick Sort →
1quickSort(a, lo, hi):
2  if lo >= hi: return
3  pivot = a[hi]; i = lo
4  for j in lo .. hi-1:
5    if a[j] < pivot:
6      swap(a[i], a[j]); i = i + 1
7  swap(a[i], a[hi])   # pivot to final spot
8  quickSort(a, lo, i-1)
9  quickSort(a, i+1, hi)
Complexity
best O(n log n)
avg O(n log n)
worst O(n²)
space O(log n)
Speed