Quick Sort
Quick sort picks a pivot element, partitions the array so all smaller elements go left and all larger go right, then recursively sorts each partition. It is in-place and O(n log n) on average — often faster than merge sort in practice due to better cache locality.
How It Works
Array: [3, 6, 8, 10, 1, 2, 1] pivot = 3 (last element)
After partition:
[1, 2, 1, 3, 6, 8, 10]
←smaller→ ↑ ←larger→
pivot is now in its final sorted position
Recurse:
left [1, 2, 1] → sort → [1, 1, 2]
right [6, 8, 10] → sort → [6, 8, 10]
Result: [1, 1, 2, 3, 6, 8, 10]Lomuto Partition Scheme
Lomuto is the simpler scheme. It uses the last element as the pivot and tracks a boundary index i that grows as smaller elements are found.
def partition(arr, lo, hi):
pivot = arr[hi] # last element is pivot
i = lo - 1 # i tracks the right edge of the "smaller" region
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] # place pivot in correct spot
return i + 1 # return pivot's final index
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) # sort left of pivot
quick_sort(arr, p + 1, hi) # sort right of pivot
return arr
nums = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(nums)) # [1, 1, 2, 3, 6, 8, 10]Random Pivot
Choosing the last element as pivot is O(n²) on already-sorted input because every partition creates one empty side. Randomising the pivot makes this pathological case astronomically unlikely.
import random
def partition_random(arr, lo, hi):
# Swap a random element to the end, then use Lomuto
rand_idx = random.randint(lo, hi)
arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
return partition(arr, lo, hi)
def quick_sort_random(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition_random(arr, lo, hi)
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
return arr
# Sorted input no longer causes O(n²)
sorted_input = list(range(1000))
print(quick_sort_random(sorted_input)[:5]) # [0, 1, 2, 3, 4]Naive Python Version (for Clarity)
Not in-place, but shows the logic without index arithmetic.
def quick_sort_naive(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort_naive(left) + middle + quick_sort_naive(right)
print(quick_sort_naive([3, 6, 8, 10, 1, 2, 1]))
# [1, 1, 2, 3, 6, 8, 10]Call Stack Depth
With random pivot, the expected recursion depth is O(log n). In the pathological case (always picking min or max), depth is O(n), hitting Python’s default recursion limit of 1000 for n > 1000. For large production use, prefer Python’s built-in sorted() (Timsort).
Complexity Table
| Case | Time | Space (stack) | Note |
|---|---|---|---|
| Best case | O(n log n) | O(log n) | Pivot always splits evenly |
| Average case | O(n log n) | O(log n) | Expected with random pivot |
| Worst case | O(n²) | O(n) | Always min/max pivot; avoid with randomisation |
| Stable | No | — | Swaps can change equal element order |
| In-place | Yes | — | No auxiliary array (call stack only) |