Quick Sort
Partition around a pivot so smaller values are left of it, then recurse each side. Average O(n log n) with tiny constants; the standard library workhorse.
- Category
- Sorting
- Time complexity
- O(n log n) avg
- Space complexity
- O(log n)
Pseudocode
quickSort(lo, hi) pivot ← A[hi] partition: smaller left pivot to final slot; recurse done
Reference implementation
def quick_sort(a, lo, hi):
if lo >= hi: return
p = partition(a, lo, hi)
quick_sort(a, lo, p - 1)
quick_sort(a, p + 1, hi)