Quick Sort Deep Dive: Partition, Pivot, and QuickSelect
Master quick sort — Lomuto and Hoare partitions, pivot strategies, worst case analysis, Dutch National Flag, QuickSelect for kth element, and comparison with merge sort.
What you'll learn
- ✓How the partition algorithm splits an array around a pivot
- ✓Lomuto vs Hoare partition — when to use each
- ✓Pivot selection strategies and how they affect performance
- ✓Why worst case is O(n^2) and how randomisation fixes it
- ✓Dutch National Flag (3-way partition) for arrays with duplicates
- ✓QuickSelect — finding the kth smallest in O(n) average
Prerequisites
- •Comfortable with array manipulation
- •Familiar with recursion
- •Understand Big-O notation
Quick sort is the fastest general-purpose sorting algorithm in practice. Its average case of O(n log n) beats merge sort on cache performance, and it sorts in-place (O(log n) stack space). The price: a worst case of O(n^2) — but smart pivot selection makes that practically impossible.
1. The Partition Algorithm
Partition is the core operation. Given an array and a pivot element, rearrange the array so that:
- All elements < pivot are on the left.
- The pivot is in its final sorted position.
- All elements > pivot are on the right.
After partition, the pivot is in its correct position and never moves again.
2. Lomuto Partition Scheme
The simpler of the two partition methods. Uses the last element as pivot and a single pointer.
def lomuto_partition(arr, lo, hi):
"""
Lomuto partition scheme.
Pivot = arr[hi] (last element).
Returns the final index of the pivot.
Time: O(n), Space: O(1)
"""
pivot = arr[hi]
i = lo # boundary of elements < pivot
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
# Place pivot in its correct position
arr[i], arr[hi] = arr[hi], arr[i]
return i
arr = [8, 3, 7, 1, 9, 2, 5]
pivot_idx = lomuto_partition(arr, 0, len(arr) - 1)
print(f"Array: {arr}, Pivot index: {pivot_idx}")
# Pivot=5, Array: [3, 1, 2, 5, 9, 7, 8], Pivot index: 3How it works:
imarks the boundary: everything beforeiis < pivot.jscans through the array.- When
arr[j] < pivot, swap it into the “less than” region and advancei. - Finally, swap the pivot into position
i.
3. Hoare Partition Scheme
Uses two pointers that move towards each other. More efficient in practice (fewer swaps on average).
def hoare_partition(arr, lo, hi):
"""
Hoare partition scheme.
Pivot = arr[lo] (first element).
Returns the partition index (pivot is NOT necessarily at this index).
Time: O(n), Space: O(1)
"""
pivot = arr[lo]
i = lo - 1
j = hi + 1
while True:
# Move i right until we find element >= pivot
i += 1
while arr[i] < pivot:
i += 1
# Move j left until we find element <= pivot
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
arr = [8, 3, 7, 1, 9, 2, 5]
p = hoare_partition(arr, 0, len(arr) - 1)
print(f"Array: {arr}, Partition index: {p}")Key difference from Lomuto:
- Hoare uses the first element as pivot.
- The return value is a partition point, not the pivot’s final position.
- On average, Hoare does 3x fewer swaps than Lomuto.
4. Quick Sort with Lomuto Partition
def quick_sort_lomuto(arr, lo=0, hi=None):
"""
Quick sort using Lomuto partition.
Time: O(n log n) average, O(n^2) worst
Space: O(log n) average stack space
"""
if hi is None:
hi = len(arr) - 1
if lo < hi:
pivot_idx = lomuto_partition(arr, lo, hi)
quick_sort_lomuto(arr, lo, pivot_idx - 1)
quick_sort_lomuto(arr, pivot_idx + 1, hi)
data = [38, 27, 43, 3, 9, 82, 10]
quick_sort_lomuto(data)
print(data) # [3, 9, 10, 27, 38, 43, 82]5. Quick Sort with Hoare Partition
def quick_sort_hoare(arr, lo=0, hi=None):
"""
Quick sort using Hoare partition.
Time: O(n log n) average, O(n^2) worst
Space: O(log n) average stack space
"""
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p)
quick_sort_hoare(arr, p + 1, hi)
data = [38, 27, 43, 3, 9, 82, 10]
quick_sort_hoare(data)
print(data) # [3, 9, 10, 27, 38, 43, 82]6. Pivot Selection Strategies
The choice of pivot determines whether quick sort runs in O(n log n) or O(n^2).
First/Last Element (Naive)
# Already shown above: arr[hi] for Lomuto, arr[lo] for Hoare
# Worst case: sorted or reverse-sorted arrays -> O(n^2)Random Pivot
import random
def randomized_partition(arr, lo, hi):
"""
Choose a random pivot and use Lomuto partition.
Expected O(n log n) regardless of input.
"""
rand_idx = random.randint(lo, hi)
arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
return lomuto_partition(arr, lo, hi)
def randomized_quick_sort(arr, lo=0, hi=None):
"""Quick sort with random pivot selection."""
if hi is None:
hi = len(arr) - 1
if lo < hi:
pivot_idx = randomized_partition(arr, lo, hi)
randomized_quick_sort(arr, lo, pivot_idx - 1)
randomized_quick_sort(arr, pivot_idx + 1, hi)
data = [1, 2, 3, 4, 5, 6, 7, 8] # sorted input
randomized_quick_sort(data)
print(data) # [1, 2, 3, 4, 5, 6, 7, 8] — still correct, but O(n log n) expectedMedian-of-Three
Choose the median of the first, middle, and last elements as pivot. This avoids worst case for sorted/reverse-sorted inputs.
def median_of_three(arr, lo, hi):
"""
Choose the median of arr[lo], arr[mid], arr[hi] as pivot.
Place it at arr[hi] for Lomuto partition.
"""
mid = (lo + hi) // 2
# Sort the three elements
if arr[lo] > arr[mid]:
arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]:
arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]:
arr[mid], arr[hi] = arr[hi], arr[mid]
# Now arr[lo] <= arr[mid] <= arr[hi]
# Place median at hi-1 position
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi]
def quick_sort_median_of_three(arr, lo=0, hi=None):
"""Quick sort with median-of-three pivot selection."""
if hi is None:
hi = len(arr) - 1
if lo < hi:
if hi - lo + 1 > 3:
median_of_three(arr, lo, hi)
pivot_idx = lomuto_partition(arr, lo, hi)
quick_sort_median_of_three(arr, lo, pivot_idx - 1)
quick_sort_median_of_three(arr, pivot_idx + 1, hi)
data = [5, 4, 3, 2, 1]
quick_sort_median_of_three(data)
print(data) # [1, 2, 3, 4, 5]7. Worst Case Analysis
Quick sort degrades to O(n^2) when the pivot is always the smallest or largest element, creating partitions of size 0 and n-1.
def demonstrate_worst_case():
"""Show why sorted input is worst case for naive pivot."""
# With last-element pivot on sorted input:
# arr = [1, 2, 3, 4, 5]
# Pivot = 5: partition = [1,2,3,4] | 5 | [] (n-1 elements on one side)
# Pivot = 4: partition = [1,2,3] | 4 | []
# ...
# Total comparisons: n + (n-1) + (n-2) + ... + 1 = O(n^2)
# With random pivot, the expected partition is roughly balanced:
# On average, pivot lands near the middle
# T(n) = 2*T(n/2) + O(n) = O(n log n)
passInputs that cause worst case:
- Already sorted (for first/last element pivot)
- Reverse sorted
- All elements equal (for Lomuto — 3-way partition fixes this)
8. Dutch National Flag — 3-Way Partition
When the array has many duplicate values, standard partition puts all equal elements on one side. The 3-way partition (Dutch National Flag algorithm) handles this by creating three regions: < pivot, == pivot, > pivot.
def three_way_partition(arr, lo, hi):
"""
Dutch National Flag partition.
Partitions arr[lo..hi] into three parts:
- arr[lo..lt-1]: elements < pivot
- arr[lt..gt]: elements == pivot
- arr[gt+1..hi]: elements > pivot
Returns (lt, gt)
"""
pivot = arr[lo]
lt = lo # boundary for < pivot
i = lo # current element
gt = hi # boundary for > pivot
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
# Don't increment i — the swapped element needs checking
else:
i += 1
return lt, gt
def quick_sort_3way(arr, lo=0, hi=None):
"""
Quick sort with 3-way partition.
Optimal for arrays with many duplicates.
Time: O(n log n) average, O(n) when all elements equal
"""
if hi is None:
hi = len(arr) - 1
if lo < hi:
lt, gt = three_way_partition(arr, lo, hi)
quick_sort_3way(arr, lo, lt - 1) # sort elements < pivot
quick_sort_3way(arr, gt + 1, hi) # sort elements > pivot
# Elements == pivot are already in final position!
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
quick_sort_3way(data)
print(data) # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
# Special case: all equal
data2 = [7, 7, 7, 7, 7]
quick_sort_3way(data2)
print(data2) # [7, 7, 7, 7, 7] — O(n) time9. QuickSelect — Kth Smallest Element
QuickSelect uses the partition function to find the kth smallest element in O(n) average time, without fully sorting the array.
def quick_select(arr, k):
"""
Find the kth smallest element (0-indexed).
Average Time: O(n)
Worst Time: O(n^2) — use randomized pivot to avoid
Does NOT modify the input array.
"""
arr = arr[:] # work on a copy
def _select(lo, hi, k):
if lo == hi:
return arr[lo]
# Random pivot for expected O(n)
rand_idx = random.randint(lo, hi)
arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
pivot_idx = lomuto_partition(arr, lo, hi)
if k == pivot_idx:
return arr[k]
elif k < pivot_idx:
return _select(lo, pivot_idx - 1, k)
else:
return _select(pivot_idx + 1, hi, k)
return _select(0, len(arr) - 1, k)
arr = [3, 2, 1, 5, 6, 4]
print(quick_select(arr, 0)) # 1 (smallest)
print(quick_select(arr, 1)) # 2 (2nd smallest)
print(quick_select(arr, 4)) # 5 (5th smallest)Finding the Kth Largest
def kth_largest(arr, k):
"""
LeetCode 215: Kth Largest Element in an Array.
k is 1-indexed (1st largest = max).
"""
# kth largest = (n-k)th smallest (0-indexed)
return quick_select(arr, len(arr) - k)
arr = [3, 2, 3, 1, 2, 4, 5, 5, 6]
print(kth_largest(arr, 4)) # 4 (sorted: [1,2,2,3,3,4,5,5,6], 4th from end = 4)Why QuickSelect is O(n) Average
After partition, we only recurse on one side. The expected work:
- First call: O(n) work
- Second call: O(n/2) expected
- Third call: O(n/4) expected
- Total: O(n + n/2 + n/4 + …) = O(2n) = O(n)
10. Tail Call Optimization
To limit stack depth to O(log n), always recurse on the smaller partition first and use a loop for the larger one.
def quick_sort_tail_optimized(arr, lo=0, hi=None):
"""
Quick sort with tail call optimization.
Worst case stack depth: O(log n) instead of O(n).
"""
if hi is None:
hi = len(arr) - 1
while lo < hi:
pivot_idx = lomuto_partition(arr, lo, hi)
# Recurse on the smaller partition, loop on the larger
if pivot_idx - lo < hi - pivot_idx:
quick_sort_tail_optimized(arr, lo, pivot_idx - 1)
lo = pivot_idx + 1 # tail call on right partition
else:
quick_sort_tail_optimized(arr, pivot_idx + 1, hi)
hi = pivot_idx - 1 # tail call on left partition
data = [5, 3, 8, 1, 9, 2, 7]
quick_sort_tail_optimized(data)
print(data) # [1, 2, 3, 5, 7, 8, 9]11. Quick Sort vs Merge Sort
| Criterion | Quick Sort | Merge Sort |
|---|---|---|
| Average time | O(n log n) | O(n log n) |
| Worst time | O(n^2) | O(n log n) |
| Space | O(log n) | O(n) |
| Stable | No | Yes |
| In-place | Yes | No |
| Cache performance | Excellent | Good |
| Linked lists | Poor | Excellent |
| Practical speed | Faster (typically) | Slower (more memory ops) |
| Parallelism | Harder | Natural |
Choose quick sort when:
- You want in-place sorting.
- Average case performance matters more than worst case.
- You are sorting arrays (not linked lists).
- Memory is limited.
Choose merge sort when:
- You need guaranteed O(n log n).
- You need stability.
- You are sorting linked lists.
- You are doing external sorting.
12. Introsort — The Best of Both Worlds
Real-world implementations (like C++ std::sort) use introsort: start with quick sort, but switch to heap sort if recursion depth exceeds 2 * log(n). This gives O(n log n) worst case with quick sort’s practical speed.
import math
def introsort(arr):
"""
Introsort: quicksort with heapsort fallback.
Time: O(n log n) guaranteed
Space: O(log n)
"""
max_depth = 2 * int(math.log2(max(len(arr), 1)))
def _introsort(lo, hi, depth):
if hi - lo <= 16:
# Insertion sort for small arrays
insertion_sort(arr, lo, hi)
return
if depth == 0:
# Switch to heapsort
heapsort_range(arr, lo, hi)
return
pivot_idx = lomuto_partition(arr, lo, hi)
_introsort(lo, pivot_idx - 1, depth - 1)
_introsort(pivot_idx + 1, hi, depth - 1)
def insertion_sort(arr, lo, hi):
for i in range(lo + 1, hi + 1):
key = arr[i]
j = i - 1
while j >= lo and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def heapsort_range(arr, lo, hi):
# Simple heapsort on arr[lo..hi]
sub = arr[lo:hi + 1]
sub.sort() # use built-in for simplicity
arr[lo:hi + 1] = sub
if len(arr) > 1:
_introsort(0, len(arr) - 1, max_depth)
data = [5, 3, 8, 1, 9, 2, 7, 4, 6, 10]
introsort(data)
print(data) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]13. Practice Problems
| Problem | Platform | Key Technique |
|---|---|---|
| Sort an Array (LC 912) | LeetCode | Quick sort implementation |
| Kth Largest Element (LC 215) | LeetCode | QuickSelect |
| Sort Colors (LC 75) | LeetCode | Dutch National Flag |
| Wiggle Sort II (LC 324) | LeetCode | QuickSelect + 3-way |
| Top K Frequent Elements (LC 347) | LeetCode | QuickSelect on frequencies |
| K Closest Points to Origin (LC 973) | LeetCode | QuickSelect |
| Find Median from Data Stream (LC 295) | LeetCode | QuickSelect concept |
| Sort Array By Parity (LC 905) | LeetCode | Partition concept |
Big-O Summary
| Algorithm | Time (avg) | Time (worst) | Space |
|---|---|---|---|
| Quick sort | O(n log n) | O(n^2) | O(log n) |
| Randomized quick sort | O(n log n) | O(n^2) unlikely | O(log n) |
| 3-way quick sort | O(n log n) | O(n^2) | O(log n) |
| QuickSelect | O(n) | O(n^2) | O(1) |
| Introsort | O(n log n) | O(n log n) | O(log n) |
Quick sort’s elegance lies in the partition step. Once you understand partition, you understand not just sorting but also selection, the Dutch National Flag problem, and a whole family of divide-and-conquer techniques. It is the algorithm that sorts the real world.
Related articles
- DSA Car Fleet Problem — Stack-Based Arrival Time Solution
Solve LeetCode 853 Car Fleet using a stack. Sort by position, compare arrival times, and count fleets. Python solution with visual trace.
- DSA Counting, Radix, and Bucket Sort: Beyond O(n log n)
Break the comparison sort barrier with counting sort, radix sort (LSD and MSD), and bucket sort — Python implementations, stability analysis, and when to use each non-comparison sort.
- DSA Merge Sort Deep Dive: Divide, Conquer, and Count
Master merge sort — recursive splitting, merging sorted halves, counting inversions, merge sort on linked lists, stability analysis, and O(n log n) guaranteed performance with Python.
- DSA Sorting Algorithms: Bubble, Insertion, Merge, Quick, Heap
A tour of the five sorting algorithms every programmer should know — their ideas, Big-O time and space, stability, and Python implementations, plus when to just use sort().