Quick Sort - Learning Module

Loading content...

0/279

Pivot Selection and Partitioning

The Heart of Quick Sort

If Quick Sort's recursive structure is its skeleton, then pivot selection and partitioning are its beating heart. The entire performance characteristic of Quick Sort — whether it runs in O(n log n) time or degrades to O(n²) — hinges on these two interconnected decisions.

In the previous page, we treated partition as a black box that magically rearranges elements. Now we open that black box and examine the machinery inside. We'll see that pivot selection is not merely an implementation detail but a fundamental algorithmic choice with profound consequences. A poor pivot turns a world-class algorithm into a poor one; a good pivot strategy unlocks Quick Sort's full potential.

This page explores the mathematics and intuition behind pivot selection, develops the partition algorithm step by step, and examines strategies that production implementations use to ensure consistent performance.

What You Will Learn

By the end of this page, you will understand (1) why the pivot choice matters so critically, (2) how the partition algorithm works in complete detail, (3) multiple strategies for selecting pivots, and (4) how to analyze the quality of a partitioning scheme. You'll be able to implement partitioning correctly and reason about its correctness.

Why Pivot Selection Matters

The pivot determines how the array is divided after partitioning. The key measure is partition balance — how evenly the elements are split between the left and right partitions.

The Ideal Case: Perfect Balance

If every pivot is the median of the subarray (the element that would be in the middle position when sorted), each partition splits the array exactly in half:

Level 0: n elements
Level 1: n/2 + n/2 elements (two subarrays)
Level 2: n/4 + n/4 + n/4 + n/4 elements (four subarrays)
...
Level log₂(n): 1 element each (n subarrays of size 1)

With O(n) work at each level (partitioning all elements at that level) and O(log n) levels, total work is O(n log n).

The Worst Case: Maximum Imbalance

If every pivot is the minimum or maximum element, one partition gets n-1 elements and the other gets 0:

Level 0: n elements
Level 1: (n-1) + 0 elements
Level 2: (n-2) + 0 elements
...
Level n-1: 1 element

With O(n) work at level 0, O(n-1) at level 1, ..., O(1) at level n-1, total work is O(n²).

Impact of Pivot Quality on Performance
Pivot Quality	Partition Ratio	Recursion Depth	Total Time
Perfect median	50% / 50%	O(log n)	O(n log n)
25th-75th percentile	25-75% split	O(log n)	O(n log n)
10th-90th percentile	10-90% split	O(log n)	O(n log n) with larger constant
Consistent extremes	0% / 100%	O(n)	O(n²)

The Remarkable Tolerance for Imperfection:

Here's a crucial insight: Quick Sort is remarkably tolerant of imperfect pivots. Even consistently choosing a 25th percentile pivot (splitting 25%/75%) maintains O(n log n) performance:

With 25%/75% splits:

Depth = log₀.₇₅(n) = log(n) / log(4/3) ≈ 3.5 log₂(n)
Still O(log n) depth, just with a larger constant

The algorithm only degrades to O(n²) when pivots are consistently near-extremes — splitting 0/n-1 or similar. This situation is rare with random data and can be engineered away with proper pivot selection strategies.

Key Insight: We don't need perfect median selection. Any reasonably-central pivot maintains O(n log n) behavior. The goal of pivot selection strategies is to avoid the pathological cases where pivots are consistently near array extremes.

The 50% Threshold

Mathematically, as long as each partition is at most some fixed fraction c < 1 of the original size, the recursion depth is O(log n). Even a 99%/1% split maintains O(log n) depth (with a large constant). Only when c approaches 1 (n-1/n splits) does depth become O(n). This is why Quick Sort is robust in practice — truly pathological pivot sequences are rare.

The Partition Operation in Detail

The partition operation is the workhorse of Quick Sort. Given a subarray and a pivot value, it rearranges the elements so that:

All elements ≤ pivot are in the left portion
The pivot is at its final position
All elements ≥ pivot are in the right portion

The Partition Contract (Formal Specification):

Input: Array A, indices low and high where low ≤ high
Output: Index pivotIndex where low ≤ pivotIndex ≤ high
Post-conditions:
  1. A[pivotIndex] = original pivot value
  2. For all i ∈ [low, pivotIndex-1]: A[i] ≤ A[pivotIndex]
  3. For all j ∈ [pivotIndex+1, high]: A[j] ≥ A[pivotIndex]
  4. The multiset of elements in A[low..high] is unchanged

Why In-Place Partitioning is Non-Trivial:

If we had unlimited extra memory, partitioning would be trivial:

1. Create two auxiliary arrays: left and right
2. For each element (except pivot):
     if element ≤ pivot: append to left
     else: append to right
3. Concatenate: left + [pivot] + right

But this uses O(n) extra space. The challenge is to partition in-place using only O(1) extra memory. This requires clever pointer manipulation and swapping.

partition-conceptual.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Conceptual Non-In-Place Partition
 * 
 * This shows the logical operation partitioning performs.
 * Actual implementations must do this in-place without extra arrays.
 */
function conceptualPartition(arr: number[], low: number, high: number): number[] {
    const pivot = arr[high]; // Choose last element as pivot
    
    const left: number[] = [];
    const right: number[] = [];
    
    for (let i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    
    // Conceptual result: left + [pivot] + right
    // Pivot is now at index left.length (0-indexed from low)
    const result = [...left, pivot, ...right];
    
    // Copy back to original array
    for (let i = 0; i < result.length; i++) {
        arr[low + i] = result[i];
    }
    
    return low + left.length; // Return pivot's final position
}
 
/**
 * The challenge: achieve the same logical result using only swaps
 * and constant extra space. This is what Lomuto and Hoare schemes do.
 */

The Key Insight for In-Place Partitioning:

In-place partitioning uses the following observation: we don't need to build separate arrays. We can maintain regions within the original array and swap elements between regions as we discover where they belong.

Imagine the array divided into conceptual regions as we process:

[low ... i] : elements ≤ pivot (processed, small)
[i+1 ... j-1] : elements > pivot (processed, large)
[j ... high-1] : unprocessed elements
[high] : pivot

As we scan through unprocessed elements, each element either:

Is ≤ pivot: expand the "small" region by swapping it in
Is > pivot: the "large" region naturally expands (no action needed)

When done processing, swap the pivot into position between the two regions.

This is the essence of the Lomuto partition scheme, which we'll examine in detail on the next page.

Pivot Selection Strategies

Since pivot quality determines performance, significant research has gone into pivot selection. Let's examine the major strategies, their tradeoffs, and when each is appropriate.

Strategy 1: Fixed Position (First or Last Element)

The simplest approach: always choose the element at a fixed position as pivot.

pivot = A[high] // Last element
// or
pivot = A[low]  // First element

Pros:

Extremely simple to implement
O(1) selection time
No additional memory

Cons:

Deterministic: a malicious input can force O(n²) behavior
Sorted or nearly-sorted arrays hit worst case (common in practice!)
Reverse-sorted arrays also hit worst case

Assessment: Unsuitable for production use alone, but understanding it is essential because many teaching examples use it for simplicity.

pivot-strategies.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Pivot Selection Strategies Comparison
 */
 
// Strategy 1: Fixed position (simple but problematic)
function fixedPivot(arr: number[], low: number, high: number): number {
    return high; // Always last element
}
 
// Strategy 2: Random selection
function randomPivot(arr: number[], low: number, high: number): number {
    const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    // Swap random element to 'high' position (if using Lomuto)
    [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
    return high;
}
 
// Strategy 3: Median-of-three
function medianOfThree(arr: number[], low: number, high: number): number {
    const mid = Math.floor((low + high) / 2);
    
    // Find median of A[low], A[mid], A[high]
    // Sort these three elements and use the middle one
    if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
    if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
    if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
    
    // Now arr[mid] is the median of three
    // Move it to high-1 position for partitioning
    [arr[mid], arr[high - 1]] = [arr[high - 1], arr[mid]];
    return high - 1;
}
 
// Strategy 4: Ninther (median of medians of three)
function ninther(arr: number[], low: number, high: number): number {
    const len = high - low + 1;
    if (len < 9) return medianOfThree(arr, low, high);
    
    const step = Math.floor(len / 9);
    // Take 9 equally-spaced samples
    // Find median of 3 groups of 3
    // Find median of those 3 medians
    // (Implementation details omitted for clarity)
    
    return high; // Placeholder
}

Strategy 2: Random Pivot Selection

Choose a random element as pivot:

pivotIndex = random(low, high)
swap(A[pivotIndex], A[high])  // Move to end for Lomuto
pivot = A[high]

Pros:

Expected O(n log n) performance regardless of input distribution
No deterministic worst-case input exists
Simple to implement

Cons:

Requires random number generation (slight overhead)
Non-deterministic: same input may sort at different speeds
Very small probability of bad performance on any given run

Assessment: Excellent general-purpose choice. The probability of O(n²) behavior on any input is vanishingly small — approximately (2/n)^n for all-bad pivot choices.

Strategy 3: Median-of-Three

Examine three elements (typically first, middle, last), choose the median:

Pros:

Deterministic with performance guarantees against sorted inputs
Low overhead (constant-time selection)
Works well on real-world data

Cons:

Can still be fooled by adversarial inputs (e.g., "median-of-three killer" sequences)
Slightly more complex implementation

Assessment: Standard in many production implementations. Excellent practical choice.

Strategy 4: Median-of-Medians (Guaranteed Linear Selection)

A theoretical algorithm that finds the true median in O(n) time, guaranteeing O(n log n) worst case.

Pros:

Eliminates O(n²) worst case entirely

Cons:

High constant factors make it slower than random selection in practice
Complex implementation

Assessment: Theoretical interest; rarely used in production. The simpler strategies work better in practice.

Pivot Selection Strategy Comparison
Strategy	Time to Select	Worst Case Avoidance	Best Use Case
Fixed (last)	O(1)	None	Teaching examples only
Random	O(1)	Probabilistic	General purpose, production
Median-of-three	O(1)	Protects sorted inputs	Production, predictable performance
Median-of-medians	O(n)	Guaranteed	Theoretical interest

Understanding the Worst Case

Let's thoroughly understand when and why Quick Sort hits its O(n²) worst case. This understanding is essential for both avoiding the worst case and for interview discussions.

When Does O(n²) Occur?

O(n²) occurs when every partition produces maximally unbalanced splits: one partition of size n-1 and another of size 0.

Classic Worst Case: Sorted Array with Last-Element Pivot

Consider sorting [1, 2, 3, 4, 5] with pivot = A[high]:

Worst Case Execution on Sorted Input
Recursion Depth	Subarray	Pivot	Left Size	Right Size
0	[1,2,3,4,5]	5	4	0
1	[1,2,3,4]	4	3	0
2	[1,2,3]	3	2	0
3	[1,2]	2	1	0
4	[1]	—	base case	—

At each level, the pivot is the maximum element, so all other elements go to the left partition. This creates:

Level 0: partition n elements → O(n)
Level 1: partition n-1 elements → O(n-1)
Level 2: partition n-2 elements → O(n-2)
...
Level n-1: base case

Total: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Reverse-Sorted Array: Same Problem

[5, 4, 3, 2, 1] with last-element pivot (1) creates the same issue — the pivot is always the minimum.

Arrays with Many Duplicates

Another subtle worst case: [3, 3, 3, 3, 3]. Every partition puts all elements on one side. Standard partitioning doesn't handle equal elements well. (This is why production implementations use 3-way partitioning for arrays with duplicates.)

Real-World Implications

Sorted and nearly-sorted arrays are common in practice: log files in timestamp order, database results with default ordering, sequential IDs, etc. Using fixed-position pivot selection on such inputs is a recipe for disaster. This is why production implementations never use fixed pivots alone.

Adversarial Inputs:

If the pivot selection is deterministic, an adversary can construct worst-case inputs. For median-of-three, "median-of-three killer" sequences exist that force O(n²).

The defense against adversarial inputs is randomization: either randomized pivot selection or shuffling the input before sorting. With randomization, no deterministic worst-case input exists — the expected performance is O(n log n) for any input.

The Security Perspective:

In some contexts (web servers processing user input, for example), a deterministic sorting algorithm with known worst-case inputs can be exploited for denial-of-service attacks. Random pivot selection is a security feature, not just a performance optimization.

Probability of Worst Case with Random Pivots:

With random pivot selection, what's the probability of hitting the worst case? It's essentially zero for large n:

For O(n²) behavior, every pivot must be near-extreme
Probability of one pivot being in worst 10%: 0.2
Probability of n consecutive worst-10% pivots: 0.2^n
For n = 1000: 0.2^1000 ≈ 10^-700 (effectively impossible)

The Partition Invariant in Depth

Understanding the partition invariant deeply is essential for implementing Quick Sort correctly and for debugging issues. Let's formalize what must be true during and after partitioning.

Before Partitioning (Pre-condition):

A[low..high] contains elements to be partitioned
A pivot has been selected (often moved to A[high] or A[low])

During Partitioning (Loop Invariant — Lomuto Scheme):

At iteration i of the main loop:

A[low..high] can be divided into regions:

  [low ... j] : elements < pivot (processed, "small")
       ↑
       j is the boundary (last small element)

  [j+1 ... i-1] : elements ≥ pivot (processed, "large")

  [i ... high-1] : unprocessed elements

  [high] : pivot element

After Partitioning (Post-condition):

A[low..pivotIndex-1] all ≤ A[pivotIndex]
A[pivotIndex] is the pivot in its final position
A[pivotIndex+1..high] all ≥ A[pivotIndex]
The multiset {A[low], ..., A[high]} is unchanged

invariant-verification.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Partition with invariant checking (for debugging/understanding)
 * 
 * This implementation includes assertions to verify the invariant
 * at each step. Do not use in production due to overhead.
 */
function partitionWithInvariantChecks(
    arr: number[], 
    low: number, 
    high: number
): number {
    const pivot = arr[high];
    let j = low - 1; // j marks the end of "small" region
    
    for (let i = low; i < high; i++) {
        // INVARIANT CHECK: all elements in arr[low..j] are < pivot
        for (let k = low; k <= j; k++) {
            console.assert(arr[k] <= pivot, 
                `Invariant violation: arr[${k}]=${arr[k]} > pivot=${pivot}`);
        }
        
        // INVARIANT CHECK: all elements in arr[j+1..i-1] are >= pivot  
        for (let k = j + 1; k < i; k++) {
            console.assert(arr[k] > pivot,
                `Invariant violation: arr[${k}]=${arr[k]} <= pivot=${pivot}`);
        }
        
        if (arr[i] <= pivot) {
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
    }
    
    // Place pivot in its final position
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    
    const pivotIndex = j + 1;
    
    // FINAL INVARIANT CHECK
    for (let k = low; k < pivotIndex; k++) {
        console.assert(arr[k] <= arr[pivotIndex],
            `Final invariant violation: left element > pivot`);
    }
    for (let k = pivotIndex + 1; k <= high; k++) {
        console.assert(arr[k] >= arr[pivotIndex],
            `Final invariant violation: right element < pivot`);
    }
    
    return pivotIndex;
}

Common Invariant Violations (Bugs):

Off-by-one in boundary initialization:
- Incorrect: j = low (should be j = low - 1)
- Symptom: First element treated incorrectly
Wrong comparison operator:
- Using < instead of <= for the pivot test
- Symptom: Equal elements cluster on one side, causing imbalance with duplicates
Forgetting to place pivot in final position:
- Symptom: Pivot remains at original position, breaks recursion
Incorrect index in final swap:
- Symptom: Pivot ends up in wrong position; invariant violated
Modifying pivot during partition:
- Symptom: Partition uses changing threshold; elements misplaced

Testing Partition Correctness:

When implementing partition, test with these cases:

[3] — single element
[3, 1] — two elements, swap needed
[1, 3] — two elements, no swap needed
[3, 1, 2] — three elements
[1, 1, 1] — all equal (tests equal-handling)
[1, 2, 3] — already sorted
[3, 2, 1] — reverse sorted

Handling Equal Elements: A Subtle Challenge

The handling of elements equal to the pivot is a subtle issue that significantly impacts performance when the array contains duplicates.

The Problem:

Consider partitioning [3, 3, 3, 3, 3] with pivot = 3.

Approach A: Send equals to one side (≤ pivot go left)

All elements ≤ 3, so all go left. Partition: [3, 3, 3, 3] | 3 | []

Left subarray has n-1 elements, right has 0. This is worst-case O(n²) behavior!

Approach B: Alternate or distribute equals

If we could distribute equal elements evenly between partitions, we'd maintain balance.

The Two-Way vs Three-Way Partition:

Standard two-way partitioning (Lomuto or Hoare) produces two partitions: elements < pivot and elements > pivot. The pivot itself is placed between them.

Three-way partitioning (Dutch National Flag problem) produces three partitions: elements < pivot, elements = pivot, and elements > pivot.

With many duplicates, three-way partitioning is dramatically superior because all equal elements are placed in the middle partition and never processed again.

Array [5,3,3,3,3,3,1] After Partitioning (pivot=3)
Scheme	Left	Middle	Right	Still to Process
Two-way (≤ left)	[1,3,3,3,3] \| 3 \| [5]	—	—	5 elements
Two-way (< left)	[1] \| 3 \| [3,3,3,3,5]	—	—	5 elements
Three-way	[1]	[3,3,3,3,3]	[5]	2 elements!

three-way-partition.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Three-Way Partition (Dutch National Flag)
 * 
 * Partitions array into three regions:
 *   [low..lt-1]    : elements < pivot
 *   [lt..gt]       : elements = pivot  
 *   [gt+1..high]   : elements > pivot
 * 
 * Returns [lt, gt] - the boundaries of the equal region
 */
function threeWayPartition(
    arr: number[], 
    low: number, 
    high: number
): [number, number] {
    const pivot = arr[low]; // Use first element as pivot
    
    let lt = low;     // Less-than boundary
    let gt = high;    // Greater-than boundary
    let i = low + 1;  // Current element
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            // Element belongs in left region
            [arr[lt], arr[i]] = [arr[i], arr[lt]];
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            // Element belongs in right region
            [arr[gt], arr[i]] = [arr[i], arr[gt]];
            gt--;
            // Don't increment i - we haven't examined the swapped element
        } else {
            // Element equals pivot, already in correct region
            i++;
        }
    }
    
    return [lt, gt];
}
 
/**
 * Quick Sort with Three-Way Partitioning
 * Optimal for arrays with many duplicates
 */
function quickSort3Way(arr: number[], low: number, high: number): void {
    if (low >= high) return;
    
    const [lt, gt] = threeWayPartition(arr, low, high);
    
    // Only recurse on elements that aren't equal to pivot
    quickSort3Way(arr, low, lt - 1);   // Elements < pivot
    quickSort3Way(arr, gt + 1, high);  // Elements > pivot
    // Elements in [lt..gt] are all equal and already in final position!
}

When to Use Three-Way Partitioning:

Arrays with many duplicate values
When values come from a small domain (e.g., sorting letters, sorting by category)
When performance on duplicates is critical

The Overhead Tradeoff:

Three-way partitioning has slightly higher overhead per comparison (more branches, more pointer updates). For arrays with all-distinct elements, it may be marginally slower than two-way partitioning.

Many production implementations detect high duplicate rates and switch to three-way partitioning adaptively, or use hybrid schemes that get the best of both worlds.

The Dutch National Flag Problem

Three-way partitioning is also known as solving the Dutch National Flag problem, named by Edsger Dijkstra. The problem asks: given an array of elements colored red, white, or blue (or three categories), rearrange them so all reds come first, then whites, then blues. This is exactly three-way partitioning where < pivot = 'red', = pivot = 'white', > pivot = 'blue'.

Practical Considerations in Real Implementations

Production-quality Quick Sort implementations incorporate many refinements beyond the basic algorithm. Understanding these helps you use library sorts effectively and implement high-performance sorts when needed.

Hybrid Approaches:

For small subarrays, the overhead of recursion and partitioning exceeds their benefit. Production implementations switch to Insertion Sort for subarrays below a threshold (typically 10-20 elements).

if (high - low < THRESHOLD) {
    insertionSort(A, low, high);
    return;
}

Insertion Sort has low overhead and is cache-efficient on small arrays. The crossover point is determined empirically for the target architecture.

Production Implementation Features

•Insertion sort cutoff — Switch to Insertion Sort for subarrays of 10-20 elements to avoid recursion overhead.
•Median-of-three (or more) — Sample multiple elements to select a better pivot, protecting against sorted/reverse-sorted inputs.
•Random pivot as fallback — If recursion depth exceeds O(log n), switch to randomized selection or Heap Sort (Introsort approach).
•Three-way partitioning — Use Dutch National Flag partition when duplicates are detected, or always for better duplicate handling.
•Tail recursion elimination — Iterate on the larger partition, recurse only on the smaller, ensuring O(log n) stack depth.
•Sentinel optimization — Place the maximum element at the array end to eliminate bounds checking in loops.

Introsort: The Pragmatic Hybrid

David Musser's Introsort (introspective sort) combines Quick Sort's average-case speed with guaranteed O(n log n) worst case:

Start with Quick Sort
Track recursion depth
If depth exceeds 2⌊log₂n⌋, switch to Heap Sort

This guarantees O(n log n) while achieving Quick Sort's practical speed in the common case. Most C++ STL implementations use Introsort.

Timsort: The Alternative

Python and Java use Timsort, a hybrid of Merge Sort and Insertion Sort optimized for real-world data that often has "runs" of sorted elements. Timsort is stable (preserves order of equal elements), whereas Quick Sort is not.

The choice between Quick Sort variants and Timsort depends on:

Is stability required? (Timsort)
Is memory constrained? (Quick Sort)
Is the data likely to have sorted runs? (Timsort)
Is the data random? (Quick Sort)

Summary: Pivot Selection and Partitioning

We've deeply explored the two critical components that determine Quick Sort's performance. Let's consolidate the key insights.

Key Takeaways

•Pivot quality determines performance — Good pivots (near median) give O(n log n); bad pivots (near extremes) give O(n²).
•Quick Sort tolerates imperfect pivots — Even 10%/90% splits maintain O(n log n); only consistently extreme splits cause O(n²).
•Fixed-position pivots are dangerous — Sorted inputs (common in practice) cause worst-case behavior with first/last element pivots.
•Random pivot selection provides probabilistic O(n log n) — No deterministic worst-case input exists; the expected case is excellent.
•Median-of-three balances simplicity and robustness — Deterministic, protects against sorted inputs, low overhead.
•Three-way partitioning handles duplicates — Essential for arrays with many equal elements; the Dutch National Flag algorithm.
•Production implementations are hybrids — They combine multiple optimizations: pivot strategies, small-array cutoffs, depth limits.

What's Next:

Now that we understand pivot selection and the conceptual partition operation, we'll examine the two classic partition implementations in detail: the Lomuto partition scheme and the Hoare partition scheme. Understanding both gives you flexibility in implementation and prepares you for interview questions about Quick Sort variants.

Page Complete

You now understand why pivot selection is critical to Quick Sort's performance and how the partition operation rearranges elements. You can reason about different pivot strategies and their tradeoffs, and you understand how to handle equal elements effectively. Next, we'll examine the specific mechanics of Lomuto and Hoare partitioning.

Pivot Selection and Partitioning

The Heart of Quick Sort

What You Will Learn

Why Pivot Selection Matters

The pivot determines how the array is divided after partitioning. The key measure is partition balance — how evenly the elements are split between the left and right partitions.

The Ideal Case: Perfect Balance

If every pivot is the median of the subarray (the element that would be in the middle position when sorted), each partition splits the array exactly in half:

Level 0: n elements
Level 1: n/2 + n/2 elements (two subarrays)
Level 2: n/4 + n/4 + n/4 + n/4 elements (four subarrays)
...
Level log₂(n): 1 element each (n subarrays of size 1)

With O(n) work at each level (partitioning all elements at that level) and O(log n) levels, total work is O(n log n).

The Worst Case: Maximum Imbalance

If every pivot is the minimum or maximum element, one partition gets n-1 elements and the other gets 0:

Level 0: n elements
Level 1: (n-1) + 0 elements
Level 2: (n-2) + 0 elements
...
Level n-1: 1 element

With O(n) work at level 0, O(n-1) at level 1, ..., O(1) at level n-1, total work is O(n²).

Impact of Pivot Quality on Performance
Pivot Quality	Partition Ratio	Recursion Depth	Total Time
Perfect median	50% / 50%	O(log n)	O(n log n)
25th-75th percentile	25-75% split	O(log n)	O(n log n)
10th-90th percentile	10-90% split	O(log n)	O(n log n) with larger constant
Consistent extremes	0% / 100%	O(n)	O(n²)

The Remarkable Tolerance for Imperfection:

Here's a crucial insight: Quick Sort is remarkably tolerant of imperfect pivots. Even consistently choosing a 25th percentile pivot (splitting 25%/75%) maintains O(n log n) performance:

With 25%/75% splits:

Depth = log₀.₇₅(n) = log(n) / log(4/3) ≈ 3.5 log₂(n)
Still O(log n) depth, just with a larger constant

The 50% Threshold

The Partition Operation in Detail

The partition operation is the workhorse of Quick Sort. Given a subarray and a pivot value, it rearranges the elements so that:

All elements ≤ pivot are in the left portion
The pivot is at its final position
All elements ≥ pivot are in the right portion

The Partition Contract (Formal Specification):

Input: Array A, indices low and high where low ≤ high
Output: Index pivotIndex where low ≤ pivotIndex ≤ high
Post-conditions:
  1. A[pivotIndex] = original pivot value
  2. For all i ∈ [low, pivotIndex-1]: A[i] ≤ A[pivotIndex]
  3. For all j ∈ [pivotIndex+1, high]: A[j] ≥ A[pivotIndex]
  4. The multiset of elements in A[low..high] is unchanged

Why In-Place Partitioning is Non-Trivial:

If we had unlimited extra memory, partitioning would be trivial:

1. Create two auxiliary arrays: left and right
2. For each element (except pivot):
     if element ≤ pivot: append to left
     else: append to right
3. Concatenate: left + [pivot] + right

But this uses O(n) extra space. The challenge is to partition in-place using only O(1) extra memory. This requires clever pointer manipulation and swapping.

partition-conceptual.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Conceptual Non-In-Place Partition
 * 
 * This shows the logical operation partitioning performs.
 * Actual implementations must do this in-place without extra arrays.
 */
function conceptualPartition(arr: number[], low: number, high: number): number[] {
    const pivot = arr[high]; // Choose last element as pivot
    
    const left: number[] = [];
    const right: number[] = [];
    
    for (let i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    
    // Conceptual result: left + [pivot] + right
    // Pivot is now at index left.length (0-indexed from low)
    const result = [...left, pivot, ...right];
    
    // Copy back to original array
    for (let i = 0; i < result.length; i++) {
        arr[low + i] = result[i];
    }
    
    return low + left.length; // Return pivot's final position
}
 
/**
 * The challenge: achieve the same logical result using only swaps
 * and constant extra space. This is what Lomuto and Hoare schemes do.
 */

The Key Insight for In-Place Partitioning:

Imagine the array divided into conceptual regions as we process:

[low ... i] : elements ≤ pivot (processed, small)
[i+1 ... j-1] : elements > pivot (processed, large)
[j ... high-1] : unprocessed elements
[high] : pivot

As we scan through unprocessed elements, each element either:

Is ≤ pivot: expand the "small" region by swapping it in
Is > pivot: the "large" region naturally expands (no action needed)

When done processing, swap the pivot into position between the two regions.

This is the essence of the Lomuto partition scheme, which we'll examine in detail on the next page.

Pivot Selection Strategies

Since pivot quality determines performance, significant research has gone into pivot selection. Let's examine the major strategies, their tradeoffs, and when each is appropriate.

Strategy 1: Fixed Position (First or Last Element)

The simplest approach: always choose the element at a fixed position as pivot.

pivot = A[high] // Last element
// or
pivot = A[low]  // First element

Pros:

Extremely simple to implement
O(1) selection time
No additional memory

Cons:

Deterministic: a malicious input can force O(n²) behavior
Sorted or nearly-sorted arrays hit worst case (common in practice!)
Reverse-sorted arrays also hit worst case

Assessment: Unsuitable for production use alone, but understanding it is essential because many teaching examples use it for simplicity.

pivot-strategies.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Pivot Selection Strategies Comparison
 */
 
// Strategy 1: Fixed position (simple but problematic)
function fixedPivot(arr: number[], low: number, high: number): number {
    return high; // Always last element
}
 
// Strategy 2: Random selection
function randomPivot(arr: number[], low: number, high: number): number {
    const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    // Swap random element to 'high' position (if using Lomuto)
    [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
    return high;
}
 
// Strategy 3: Median-of-three
function medianOfThree(arr: number[], low: number, high: number): number {
    const mid = Math.floor((low + high) / 2);
    
    // Find median of A[low], A[mid], A[high]
    // Sort these three elements and use the middle one
    if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
    if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
    if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
    
    // Now arr[mid] is the median of three
    // Move it to high-1 position for partitioning
    [arr[mid], arr[high - 1]] = [arr[high - 1], arr[mid]];
    return high - 1;
}
 
// Strategy 4: Ninther (median of medians of three)
function ninther(arr: number[], low: number, high: number): number {
    const len = high - low + 1;
    if (len < 9) return medianOfThree(arr, low, high);
    
    const step = Math.floor(len / 9);
    // Take 9 equally-spaced samples
    // Find median of 3 groups of 3
    // Find median of those 3 medians
    // (Implementation details omitted for clarity)
    
    return high; // Placeholder
}

Strategy 2: Random Pivot Selection

Choose a random element as pivot:

pivotIndex = random(low, high)
swap(A[pivotIndex], A[high])  // Move to end for Lomuto
pivot = A[high]

Pros:

Expected O(n log n) performance regardless of input distribution
No deterministic worst-case input exists
Simple to implement

Cons:

Requires random number generation (slight overhead)
Non-deterministic: same input may sort at different speeds
Very small probability of bad performance on any given run

Assessment: Excellent general-purpose choice. The probability of O(n²) behavior on any input is vanishingly small — approximately (2/n)^n for all-bad pivot choices.

Strategy 3: Median-of-Three

Examine three elements (typically first, middle, last), choose the median:

Pros:

Deterministic with performance guarantees against sorted inputs
Low overhead (constant-time selection)
Works well on real-world data

Cons:

Can still be fooled by adversarial inputs (e.g., "median-of-three killer" sequences)
Slightly more complex implementation

Assessment: Standard in many production implementations. Excellent practical choice.

Strategy 4: Median-of-Medians (Guaranteed Linear Selection)

A theoretical algorithm that finds the true median in O(n) time, guaranteeing O(n log n) worst case.

Pros:

Eliminates O(n²) worst case entirely

Cons:

High constant factors make it slower than random selection in practice
Complex implementation

Assessment: Theoretical interest; rarely used in production. The simpler strategies work better in practice.

Pivot Selection Strategy Comparison
Strategy	Time to Select	Worst Case Avoidance	Best Use Case
Fixed (last)	O(1)	None	Teaching examples only
Random	O(1)	Probabilistic	General purpose, production
Median-of-three	O(1)	Protects sorted inputs	Production, predictable performance
Median-of-medians	O(n)	Guaranteed	Theoretical interest

Understanding the Worst Case

Let's thoroughly understand when and why Quick Sort hits its O(n²) worst case. This understanding is essential for both avoiding the worst case and for interview discussions.

When Does O(n²) Occur?

O(n²) occurs when every partition produces maximally unbalanced splits: one partition of size n-1 and another of size 0.

Classic Worst Case: Sorted Array with Last-Element Pivot

Consider sorting [1, 2, 3, 4, 5] with pivot = A[high]:

Worst Case Execution on Sorted Input
Recursion Depth	Subarray	Pivot	Left Size	Right Size
0	[1,2,3,4,5]	5	4	0
1	[1,2,3,4]	4	3	0
2	[1,2,3]	3	2	0
3	[1,2]	2	1	0
4	[1]	—	base case	—

At each level, the pivot is the maximum element, so all other elements go to the left partition. This creates:

Level 0: partition n elements → O(n)
Level 1: partition n-1 elements → O(n-1)
Level 2: partition n-2 elements → O(n-2)
...
Level n-1: base case

Total: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Reverse-Sorted Array: Same Problem

[5, 4, 3, 2, 1] with last-element pivot (1) creates the same issue — the pivot is always the minimum.

Arrays with Many Duplicates

Real-World Implications

Adversarial Inputs:

If the pivot selection is deterministic, an adversary can construct worst-case inputs. For median-of-three, "median-of-three killer" sequences exist that force O(n²).

The Security Perspective:

Probability of Worst Case with Random Pivots:

With random pivot selection, what's the probability of hitting the worst case? It's essentially zero for large n:

For O(n²) behavior, every pivot must be near-extreme
Probability of one pivot being in worst 10%: 0.2
Probability of n consecutive worst-10% pivots: 0.2^n
For n = 1000: 0.2^1000 ≈ 10^-700 (effectively impossible)

The Partition Invariant in Depth

Understanding the partition invariant deeply is essential for implementing Quick Sort correctly and for debugging issues. Let's formalize what must be true during and after partitioning.

Before Partitioning (Pre-condition):

A[low..high] contains elements to be partitioned
A pivot has been selected (often moved to A[high] or A[low])

During Partitioning (Loop Invariant — Lomuto Scheme):

At iteration i of the main loop:

A[low..high] can be divided into regions:

  [low ... j] : elements < pivot (processed, "small")
       ↑
       j is the boundary (last small element)

  [j+1 ... i-1] : elements ≥ pivot (processed, "large")

  [i ... high-1] : unprocessed elements

  [high] : pivot element

After Partitioning (Post-condition):

A[low..pivotIndex-1] all ≤ A[pivotIndex]
A[pivotIndex] is the pivot in its final position
A[pivotIndex+1..high] all ≥ A[pivotIndex]
The multiset {A[low], ..., A[high]} is unchanged

invariant-verification.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Partition with invariant checking (for debugging/understanding)
 * 
 * This implementation includes assertions to verify the invariant
 * at each step. Do not use in production due to overhead.
 */
function partitionWithInvariantChecks(
    arr: number[], 
    low: number, 
    high: number
): number {
    const pivot = arr[high];
    let j = low - 1; // j marks the end of "small" region
    
    for (let i = low; i < high; i++) {
        // INVARIANT CHECK: all elements in arr[low..j] are < pivot
        for (let k = low; k <= j; k++) {
            console.assert(arr[k] <= pivot, 
                `Invariant violation: arr[${k}]=${arr[k]} > pivot=${pivot}`);
        }
        
        // INVARIANT CHECK: all elements in arr[j+1..i-1] are >= pivot  
        for (let k = j + 1; k < i; k++) {
            console.assert(arr[k] > pivot,
                `Invariant violation: arr[${k}]=${arr[k]} <= pivot=${pivot}`);
        }
        
        if (arr[i] <= pivot) {
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
    }
    
    // Place pivot in its final position
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    
    const pivotIndex = j + 1;
    
    // FINAL INVARIANT CHECK
    for (let k = low; k < pivotIndex; k++) {
        console.assert(arr[k] <= arr[pivotIndex],
            `Final invariant violation: left element > pivot`);
    }
    for (let k = pivotIndex + 1; k <= high; k++) {
        console.assert(arr[k] >= arr[pivotIndex],
            `Final invariant violation: right element < pivot`);
    }
    
    return pivotIndex;
}

Common Invariant Violations (Bugs):

Off-by-one in boundary initialization:
- Incorrect: j = low (should be j = low - 1)
- Symptom: First element treated incorrectly
Wrong comparison operator:
- Using < instead of <= for the pivot test
- Symptom: Equal elements cluster on one side, causing imbalance with duplicates
Forgetting to place pivot in final position:
- Symptom: Pivot remains at original position, breaks recursion
Incorrect index in final swap:
- Symptom: Pivot ends up in wrong position; invariant violated
Modifying pivot during partition:
- Symptom: Partition uses changing threshold; elements misplaced

Testing Partition Correctness:

When implementing partition, test with these cases:

[3] — single element
[3, 1] — two elements, swap needed
[1, 3] — two elements, no swap needed
[3, 1, 2] — three elements
[1, 1, 1] — all equal (tests equal-handling)
[1, 2, 3] — already sorted
[3, 2, 1] — reverse sorted

Handling Equal Elements: A Subtle Challenge

The handling of elements equal to the pivot is a subtle issue that significantly impacts performance when the array contains duplicates.

The Problem:

Consider partitioning [3, 3, 3, 3, 3] with pivot = 3.

Approach A: Send equals to one side (≤ pivot go left)

All elements ≤ 3, so all go left. Partition: [3, 3, 3, 3] | 3 | []

Left subarray has n-1 elements, right has 0. This is worst-case O(n²) behavior!

Approach B: Alternate or distribute equals

If we could distribute equal elements evenly between partitions, we'd maintain balance.

The Two-Way vs Three-Way Partition:

Standard two-way partitioning (Lomuto or Hoare) produces two partitions: elements < pivot and elements > pivot. The pivot itself is placed between them.

Three-way partitioning (Dutch National Flag problem) produces three partitions: elements < pivot, elements = pivot, and elements > pivot.

With many duplicates, three-way partitioning is dramatically superior because all equal elements are placed in the middle partition and never processed again.

Array [5,3,3,3,3,3,1] After Partitioning (pivot=3)
Scheme	Left	Middle	Right	Still to Process
Two-way (≤ left)	[1,3,3,3,3] \| 3 \| [5]	—	—	5 elements
Two-way (< left)	[1] \| 3 \| [3,3,3,3,5]	—	—	5 elements
Three-way	[1]	[3,3,3,3,3]	[5]	2 elements!

three-way-partition.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Three-Way Partition (Dutch National Flag)
 * 
 * Partitions array into three regions:
 *   [low..lt-1]    : elements < pivot
 *   [lt..gt]       : elements = pivot  
 *   [gt+1..high]   : elements > pivot
 * 
 * Returns [lt, gt] - the boundaries of the equal region
 */
function threeWayPartition(
    arr: number[], 
    low: number, 
    high: number
): [number, number] {
    const pivot = arr[low]; // Use first element as pivot
    
    let lt = low;     // Less-than boundary
    let gt = high;    // Greater-than boundary
    let i = low + 1;  // Current element
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            // Element belongs in left region
            [arr[lt], arr[i]] = [arr[i], arr[lt]];
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            // Element belongs in right region
            [arr[gt], arr[i]] = [arr[i], arr[gt]];
            gt--;
            // Don't increment i - we haven't examined the swapped element
        } else {
            // Element equals pivot, already in correct region
            i++;
        }
    }
    
    return [lt, gt];
}
 
/**
 * Quick Sort with Three-Way Partitioning
 * Optimal for arrays with many duplicates
 */
function quickSort3Way(arr: number[], low: number, high: number): void {
    if (low >= high) return;
    
    const [lt, gt] = threeWayPartition(arr, low, high);
    
    // Only recurse on elements that aren't equal to pivot
    quickSort3Way(arr, low, lt - 1);   // Elements < pivot
    quickSort3Way(arr, gt + 1, high);  // Elements > pivot
    // Elements in [lt..gt] are all equal and already in final position!
}

When to Use Three-Way Partitioning:

Arrays with many duplicate values
When values come from a small domain (e.g., sorting letters, sorting by category)
When performance on duplicates is critical

The Overhead Tradeoff:

Three-way partitioning has slightly higher overhead per comparison (more branches, more pointer updates). For arrays with all-distinct elements, it may be marginally slower than two-way partitioning.

Many production implementations detect high duplicate rates and switch to three-way partitioning adaptively, or use hybrid schemes that get the best of both worlds.

The Dutch National Flag Problem

Practical Considerations in Real Implementations

Hybrid Approaches:

For small subarrays, the overhead of recursion and partitioning exceeds their benefit. Production implementations switch to Insertion Sort for subarrays below a threshold (typically 10-20 elements).

if (high - low < THRESHOLD) {
    insertionSort(A, low, high);
    return;
}

Insertion Sort has low overhead and is cache-efficient on small arrays. The crossover point is determined empirically for the target architecture.

Production Implementation Features

•Insertion sort cutoff — Switch to Insertion Sort for subarrays of 10-20 elements to avoid recursion overhead.
•Median-of-three (or more) — Sample multiple elements to select a better pivot, protecting against sorted/reverse-sorted inputs.
•Random pivot as fallback — If recursion depth exceeds O(log n), switch to randomized selection or Heap Sort (Introsort approach).
•Three-way partitioning — Use Dutch National Flag partition when duplicates are detected, or always for better duplicate handling.
•Tail recursion elimination — Iterate on the larger partition, recurse only on the smaller, ensuring O(log n) stack depth.
•Sentinel optimization — Place the maximum element at the array end to eliminate bounds checking in loops.

Introsort: The Pragmatic Hybrid

David Musser's Introsort (introspective sort) combines Quick Sort's average-case speed with guaranteed O(n log n) worst case:

Start with Quick Sort
Track recursion depth
If depth exceeds 2⌊log₂n⌋, switch to Heap Sort

This guarantees O(n log n) while achieving Quick Sort's practical speed in the common case. Most C++ STL implementations use Introsort.

Timsort: The Alternative

The choice between Quick Sort variants and Timsort depends on:

Is stability required? (Timsort)
Is memory constrained? (Quick Sort)
Is the data likely to have sorted runs? (Timsort)
Is the data random? (Quick Sort)

Summary: Pivot Selection and Partitioning

We've deeply explored the two critical components that determine Quick Sort's performance. Let's consolidate the key insights.

Key Takeaways

•Pivot quality determines performance — Good pivots (near median) give O(n log n); bad pivots (near extremes) give O(n²).
•Quick Sort tolerates imperfect pivots — Even 10%/90% splits maintain O(n log n); only consistently extreme splits cause O(n²).
•Fixed-position pivots are dangerous — Sorted inputs (common in practice) cause worst-case behavior with first/last element pivots.
•Random pivot selection provides probabilistic O(n log n) — No deterministic worst-case input exists; the expected case is excellent.
•Median-of-three balances simplicity and robustness — Deterministic, protects against sorted inputs, low overhead.
•Three-way partitioning handles duplicates — Essential for arrays with many equal elements; the Dutch National Flag algorithm.
•Production implementations are hybrids — They combine multiple optimizations: pivot strategies, small-array cutoffs, depth limits.

What's Next:

Page Complete