Quick Sort
Pick a pivot.
Quick sort is another divide and conquer sort, and one of the fastest in practice. Pick one item, called the pivot. Put everything smaller on its left, and everything bigger on its right. Now the pivot is in its final place. Then quick sort each side.

- Pick a pivot
- Smaller left, bigger right
- Repeat on each side
A simple quick sort
This version is written for clarity. We pick the middle item as the pivot. Three list comprehensions split the items into smaller, equal, and bigger. Then we quick sort the two outer groups, and join everything together. Run it.
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
smaller = [x for x in nums if x < pivot]
equal = [x for x in nums if x == pivot]
bigger = [x for x in nums if x > pivot]
return quick_sort(smaller) + equal + quick_sort(bigger)
print(quick_sort([33, 10, 55, 71, 29, 3, 18, 42]))[3, 10, 18, 29, 33, 42, 55, 71]
Quick sort cost
On average, the pivot splits the list roughly in half, so quick sort is O of N log N, and very fast. But if the pivot is always the smallest or biggest item, the splits are lopsided, and it becomes O of N squared. Picking a random pivot, or the middle, makes that very unlikely.
| key | value |
|---|---|
| Average | O(n log n) |
| Worst | O(n²), bad pivots |
| Fix | random or middle pivot |
| In practice | very fast |
Summary
Quick sort places a pivot, splits around it, and recurses. Average O of N log N. Next, sorting by anything you like, with a key.
Key takeaways- Pick a pivot
- Partition around it
- Average O(n log n)