Quick Sort
DSA · Sorting Algorithms
Theory
Quick sort picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts both sides. With good pivots each partition splits the work roughly in half, giving O(n log n) average time. A bad pivot (for example always the smallest element) gives O(n²), which random or median-of-three pivots avoid. The in-place version uses only O(log n) stack space.
Why we use it
It is usually the fastest general-purpose comparison sort in practice because of its cache-friendly in-place partitioning.
When to use it
Use it for large in-memory arrays when stability is not required. Quickselect, its cousin, finds the kth smallest element in O(n) average.
How it works
- quickSort(arr, low, high)
- low < high? Yes: Choose a pivot. No: Return (0 or 1 element).
- Partition: smaller left of pivot, larger right
- Pivot is now in its final position p
- quickSort(low, p-1) and quickSort(p+1, high)
- Done
Syntax
quick_sort(arr, lo, hi):
if lo < hi:
p = partition(arr, lo, hi)
quick_sort(arr, lo, p-1)
quick_sort(arr, p+1, hi)
Time: O(n log n) avg, O(n²) worst Space: O(log n) Not stableExample
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
def quick_sort(arr, lo, hi):
if lo < hi:
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
return arr
data = [10, 7, 8, 9, 1, 5]
print(quick_sort(data, 0, len(data) - 1))Key points
- Partition around a pivot
- Average O(n log n), worst O(n²)
- Random pivots avoid the worst case
- In place but not stable