Quick Sort
Efficient in-place sorting using partitioning and pivot selection. Understand average vs worst case performance.
Quick sort is often the fastest sorting algorithm in practice. It uses a divide-and-conquer approach with a key operation called partitioning: choosing a pivot element and rearranging the array so all smaller elements are on one side and all larger elements are on the other.
How It Works
- Choose a pivot element
- Partition: Move elements smaller than pivot to the left, larger to the right
- Recursively sort the left and right partitions
- No merge needed—the array is sorted in place!
Sorting [10, 80, 30, 90, 40, 50, 70]:
Step 1: Choose pivot (70) and partition
[10, 80, 30, 90, 40, 50, 70]
↓ partition around 70
[10, 30, 40, 50, 70, 90, 80]
smaller ← → larger
Step 2: Recursively sort left [10, 30, 40, 50]
Already nearly sorted...
[10, 30, 40, 50]
Step 3: Recursively sort right [90, 80]
[80, 90]
Final: [10, 30, 40, 50, 70, 80, 90]
The Partition Operation
The partition operation is the heart of quicksort:
fn partition(arr: &mut [i32], low: usize, high: usize) -> usize {
let pivot = arr[high]; // Choose last element as pivot
let mut i = low; // Index of smaller element
for j in low..high {
if arr[j] <= pivot {
arr.swap(i, j);
i += 1;
}
}
// Place pivot in correct position
arr.swap(i, high);
i
}
Partitioning [10, 80, 30, 90, 40, 50, 70] with pivot = 70:
Initial: i = 0
[10, 80, 30, 90, 40, 50, 70]
j→
j=0: 10 <= 70, swap arr[0] with arr[0], i=1
[10, 80, 30, 90, 40, 50, 70]
↑
j=1: 80 > 70, skip
j=2: 30 <= 70, swap arr[1] with arr[2], i=2
[10, 30, 80, 90, 40, 50, 70]
↑
j=3: 90 > 70, skip
j=4: 40 <= 70, swap arr[2] with arr[4], i=3
[10, 30, 40, 90, 80, 50, 70]
↑
j=5: 50 <= 70, swap arr[3] with arr[5], i=4
[10, 30, 40, 50, 80, 90, 70]
↑
Final: swap arr[4] with arr[6] (pivot)
[10, 30, 40, 50, 70, 90, 80]
↑
pivot in place
Implementation
fn quick_sort(arr: &mut [i32]) {
let len = arr.len();
if len <= 1 {
return;
}
quick_sort_helper(arr, 0, len - 1);
}
fn quick_sort_helper(arr: &mut [i32], low: usize, high: usize) {
if low < high {
// Partition and get pivot index
let pivot_idx = partition(arr, low, high);
// Recursively sort partitions
if pivot_idx > 0 {
quick_sort_helper(arr, low, pivot_idx - 1);
}
if pivot_idx < high {
quick_sort_helper(arr, pivot_idx + 1, high);
}
}
}
fn partition(arr: &mut [i32], low: usize, high: usize) -> usize {
let pivot = arr[high];
let mut i = low;
for j in low..high {
if arr[j] <= pivot {
arr.swap(i, j);
i += 1;
}
}
arr.swap(i, high);
i
}
fn main() {
let mut arr = vec![10, 80, 30, 90, 40, 50, 70];
quick_sort(&mut arr);
println!("{:?}", arr);
}
Time Complexity
Best and Average Case: O(n log n) When the pivot divides the array roughly in half:
T(n) = 2T(n/2) + O(n) → O(n log n)
Worst Case: O(n²) When the pivot is always the smallest or largest element:
T(n) = T(n-1) + O(n) → O(n²)
This happens with:
- Already sorted arrays (if using first/last pivot)
- All equal elements
- Reverse sorted arrays
Worst Case Matters
The O(n²) worst case can be triggered by adversarial input. For security-sensitive applications, randomized pivot selection or introsort (switches to heapsort when recursion is too deep) prevents guaranteed worst-case behavior.
Pivot Selection Strategies
Last Element (Simple)
let pivot = arr[high];
Simple but vulnerable to sorted input.
Random Pivot
use rand::Rng;
fn partition_random(arr: &mut [i32], low: usize, high: usize) -> usize {
let mut rng = rand::thread_rng();
let rand_idx = rng.gen_range(low..=high);
arr.swap(rand_idx, high);
partition(arr, low, high)
}
Avoids worst case with high probability.
Median of Three
fn median_of_three(arr: &mut [i32], low: usize, high: usize) -> usize {
let mid = low + (high - low) / 2;
// Sort low, mid, high
if arr[low] > arr[mid] {
arr.swap(low, mid);
}
if arr[mid] > arr[high] {
arr.swap(mid, high);
}
if arr[low] > arr[mid] {
arr.swap(low, mid);
}
// Move median to high - 1
arr.swap(mid, high - 1);
high - 1
}
Good balance of simplicity and robustness.
Three-Way Partition (Dutch National Flag)
Handles duplicate elements efficiently:
fn quick_sort_3way(arr: &mut [i32]) {
let len = arr.len();
if len <= 1 {
return;
}
quick_sort_3way_helper(arr, 0, len - 1);
}
fn quick_sort_3way_helper(arr: &mut [i32], low: usize, high: usize) {
if low >= high {
return;
}
let pivot = arr[low];
let mut lt = low; // arr[low..lt] < pivot
let mut i = low + 1; // arr[lt..i] == pivot
let mut gt = high; // arr[gt+1..=high] > pivot
while i <= gt {
if arr[i] < pivot {
arr.swap(lt, i);
lt += 1;
i += 1;
} else if arr[i] > pivot {
arr.swap(i, gt);
if gt == 0 {
break;
}
gt -= 1;
} else {
i += 1;
}
}
if lt > 0 {
quick_sort_3way_helper(arr, low, lt - 1);
}
if gt < high {
quick_sort_3way_helper(arr, gt + 1, high);
}
}
fn main() {
let mut arr = vec![3, 5, 2, 3, 8, 3, 1, 3, 5];
quick_sort_3way(&mut arr);
println!("{:?}", arr);
}
Why Three-Way?
Standard quicksort has O(n²) performance on arrays with many duplicates. Three-way partitioning groups equal elements together, achieving O(n) for all-equal arrays and improving average case for data with duplicates.
Space Complexity
- Average case: O(log n) for recursion stack
- Worst case: O(n) for recursion stack (unbalanced partitions)
Tail recursion optimization can reduce worst-case stack space:
fn quick_sort_tail_opt(arr: &mut [i32], mut low: usize, mut high: usize) {
while low < high {
let pivot_idx = partition(arr, low, high);
// Recurse on smaller partition, iterate on larger
if pivot_idx - low < high - pivot_idx {
if pivot_idx > 0 {
quick_sort_tail_opt(arr, low, pivot_idx - 1);
}
low = pivot_idx + 1;
} else {
if pivot_idx < high {
quick_sort_tail_opt(arr, pivot_idx + 1, high);
}
if pivot_idx == 0 {
break;
}
high = pivot_idx - 1;
}
}
}
Properties
| Property | Quick Sort | |----------|------------| | Time (best/avg) | O(n log n) | | Time (worst) | O(n²) | | Space | O(log n) average | | Stable | No | | In-place | Yes | | Adaptive | No |
Why Quick Sort is Fast
- In-place: No extra arrays (unlike merge sort)
- Cache-friendly: Sequential memory access in partition
- Low overhead: Simple operations, no merging
- Small constants: Fewer operations per comparison
Real-world benchmarks often show quicksort 2-3x faster than merge sort for arrays.
Quick Select: Finding k-th Smallest
Partition can find the k-th element in O(n) average:
fn quick_select(arr: &mut [i32], k: usize) -> i32 {
let mut low = 0;
let mut high = arr.len() - 1;
loop {
let pivot_idx = partition(arr, low, high);
if pivot_idx == k {
return arr[k];
} else if pivot_idx < k {
low = pivot_idx + 1;
} else {
if pivot_idx == 0 {
break;
}
high = pivot_idx - 1;
}
}
arr[k]
}
fn main() {
let mut arr = vec![3, 1, 4, 1, 5, 9, 2, 6, 5];
let kth = quick_select(&mut arr, 4);
println!("5th smallest: {}", kth); // 4
}
Comparison with Merge Sort
| Aspect | Quick Sort | Merge Sort | |--------|------------|------------| | Average time | O(n log n) | O(n log n) | | Worst time | O(n²) | O(n log n) | | Space | O(log n) | O(n) | | In-place | Yes | No | | Stable | No | Yes | | Cache | Excellent | Good | | Practical speed | Usually faster | More predictable |
Key Takeaways
- Quick sort partitions around a pivot, then recursively sorts
- Average O(n log n), but worst case O(n²)
- In-place sorting with excellent cache performance
- Pivot selection crucial: random or median-of-three recommended
- Three-way partition handles duplicates well
- Often the fastest sorting algorithm in practice
- Not stable (equal elements may be reordered)
Quick sort's combination of simplicity, in-place operation, and cache efficiency makes it the go-to choice for general-purpose sorting in many standard libraries.