Quick Sort - Learning Module

Loading content...

0/279

Lomuto vs Hoare Partition Schemes

Two Paths to the Same Goal

The partition operation is the heart of Quick Sort, and there are two classic ways to implement it: the Lomuto partition scheme and the Hoare partition scheme. Both achieve the same logical result — rearranging elements around a pivot — but they differ significantly in their mechanics, performance characteristics, and ease of implementation.

Nico Lomuto's scheme (popularized through textbooks like CLRS) is simpler to understand and implement correctly. It uses a single scan through the array, maintaining a clear invariant that's easy to verify.

Tony Hoare's original scheme is more efficient, making approximately half as many swaps on average, but its mechanics are subtler and the invariants more nuanced. It's the scheme Hoare invented alongside Quick Sort itself.

Understanding both schemes is essential: Lomuto for clarity and teaching, Hoare for performance-critical implementations. Many interview questions explore the differences, and production implementations often use Hoare's scheme or its variants for the performance benefit.

What You Will Learn

By the end of this page, you will (1) be able to implement both Lomuto and Hoare partition schemes correctly, (2) understand the invariants each maintains, (3) recognize the performance differences between them, and (4) know when to choose one over the other.

Lomuto Partition Scheme

The Lomuto partition scheme is characterized by its simplicity and clarity. It uses the last element as the pivot and scans from left to right, maintaining a boundary between elements ≤ pivot and elements > pivot.

Key Characteristics:

Pivot is always the last element (A[high])
Single scan from left to right
Maintains boundary j: everything in A[low..j] is ≤ pivot
Returns the pivot's final position after placing it

The Invariant:

At any point during the scan, the array is divided into four regions:

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

As we scan, each element is classified and moved to the appropriate region.

lomuto-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
56
57
58
59
60
61
62
63
/**
 * Lomuto Partition Scheme
 * 
 * Algorithm:
 * 1. Select the last element as pivot
 * 2. Initialize boundary j = low - 1 (nothing in "small" region yet)
 * 3. Scan elements from low to high-1
 *    - If element ≤ pivot: expand "small" region and swap element in
 *    - If element > pivot: "large" region naturally expands
 * 4. Place pivot between the two regions
 * 5. Return pivot's position
 * 
 * @param arr - The array to partition
 * @param low - Starting index (inclusive)
 * @param high - Ending index (inclusive), arr[high] is the pivot
 * @returns The final index of the pivot
 */
function lomutoPartition(arr: number[], low: number, high: number): number {
    const pivot = arr[high]; // Step 1: Last element is pivot
    
    let j = low - 1; // Step 2: j is the boundary of "small" region
                     // A[low..j] will contain elements ≤ pivot
                     // Initially empty (j < low)
    
    // Step 3: Scan through all elements except pivot
    for (let i = low; i < high; i++) {
        // INVARIANT at this point:
        // - A[low..j] has elements ≤ pivot
        // - A[j+1..i-1] has elements > pivot
        // - A[i..high-1] is unprocessed
        // - A[high] is pivot
        
        if (arr[i] <= pivot) {
            // This element belongs in the "small" region
            j++; // Expand the "small" region
            
            // Swap arr[i] into the "small" region
            // arr[j] was the first element of "large" region (or unprocessed)
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
        // If arr[i] > pivot, no action needed
        // The "large" region naturally expands to include it
    }
    
    // Step 4: Place pivot in its final position
    // The pivot should go right after the "small" region
    // That position is j + 1
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    
    // Step 5: Return pivot's final position
    return j + 1;
}
 
/**
 * Complete Quick Sort using Lomuto Partition
 */
function quickSortLomuto(arr: number[], low: number, high: number): void {
    if (low < high) {
        const pivotIndex = lomutoPartition(arr, low, high);
        quickSortLomuto(arr, low, pivotIndex - 1);
        quickSortLomuto(arr, pivotIndex + 1, high);
    }
}

Trace Through an Example:

Let's partition [8, 3, 7, 1, 5, 2, 6, 4] with pivot = 4 (last element).

Lomuto Partition Trace: [8, 3, 7, 1, 5, 2, 6, 4], pivot = 4
Step	i	j	A[i]	A[i] ≤ 4?	Action	Array State
Init	—	-1	—	—	—	[8, 3, 7, 1, 5, 2, 6, 4]
1	0	-1	8	No	Skip	[8, 3, 7, 1, 5, 2, 6, 4]
2	1	-1	3	Yes	j++, swap(0,1)	[3, 8, 7, 1, 5, 2, 6, 4]
3	2	0	7	No	Skip	[3, 8, 7, 1, 5, 2, 6, 4]
4	3	0	1	Yes	j++, swap(1,3)	[3, 1, 7, 8, 5, 2, 6, 4]
5	4	1	5	No	Skip	[3, 1, 7, 8, 5, 2, 6, 4]
6	5	1	2	Yes	j++, swap(2,5)	[3, 1, 2, 8, 5, 7, 6, 4]
7	6	2	6	No	Skip	[3, 1, 2, 8, 5, 7, 6, 4]
Final	—	2	—	—	swap(3,7)	[3, 1, 2, 4, 5, 7, 6, 8]

Final Result: [3, 1, 2, 4, 5, 7, 6, 8]

Pivot index returned: 3
Left partition: [3, 1, 2] — all ≤ 4 ✓
Right partition: [5, 7, 6, 8] — all > 4 ✓
Pivot 4 is in its final sorted position ✓

Analysis of Lomuto:

Comparisons: Exactly n-1 comparisons (one per element except pivot)
Swaps: O(n) in the worst case (when all elements < pivot)
Simplicity: Very straightforward invariant and logic
Stability: Not stable (swaps can change relative order of equal elements)

Lomuto's Weakness: Duplicates

Lomuto partition places all elements equal to the pivot on one side (the left, since we use ≤). With many duplicates, this causes unbalanced partitions. For [3, 3, 3, 3, 3] with pivot 3, ALL elements go left, creating n-1 / 0 splits — worst-case O(n²) behavior.

Hoare Partition Scheme

The Hoare partition scheme is Tony Hoare's original algorithm, developed alongside Quick Sort itself in 1959. It uses two pointers that scan from opposite ends toward the center, swapping elements that are on the wrong side.

Key Characteristics:

Uses two pointers: i starts from left, j starts from right
Pointers move toward each other until they cross
Swaps pairs of misplaced elements
Pivot can be any element (often first or middle)
Returns a partition point — but the pivot may NOT be at this position

Important Distinction: Unlike Lomuto, Hoare's scheme doesn't necessarily place the pivot in its final position. It guarantees that elements in A[low..p] are ≤ pivot and elements in A[p+1..high] are ≥ pivot, but the pivot itself might be in either partition.

This means the recursive calls in Quick Sort with Hoare partition are slightly different:

QuickSort(A, low, p)     // NOT p-1
QuickSort(A, p+1, high)

hoare-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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Hoare Partition Scheme
 * 
 * Algorithm:
 * 1. Select a pivot (often first or middle element)
 * 2. Initialize two pointers: i at low-1, j at high+1
 * 3. Loop:
 *    a. Move i right until A[i] >= pivot
 *    b. Move j left until A[j] <= pivot  
 *    c. If i < j: swap A[i] and A[j]
 *    d. If i >= j: return j as the partition point
 * 
 * @param arr - The array to partition
 * @param low - Starting index (inclusive)
 * @param high - Ending index (inclusive)
 * @returns The partition point p where A[low..p] ≤ pivot, A[p+1..high] ≥ pivot
 */
function hoarePartition(arr: number[], low: number, high: number): number {
    // Step 1: Select pivot (using first element)
    // Using middle element is also common and protects against sorted inputs
    const pivot = arr[low];
    // Alternative: const pivot = arr[Math.floor((low + high) / 2)];
    
    // Step 2: Initialize pointers outside the array bounds
    // They will be moved before first access
    let i = low - 1;
    let j = high + 1;
    
    // Step 3: Main loop
    while (true) {
        // Step 3a: Move i right, find element >= pivot
        do {
            i++;
        } while (arr[i] < pivot);
        
        // Step 3b: Move j left, find element <= pivot
        do {
            j--;
        } while (arr[j] > pivot);
        
        // Step 3c & 3d: Check if pointers crossed
        if (i >= j) {
            // Pointers have crossed or met
            // j is the partition point
            return j;
        }
        
        // Pointers haven't crossed: swap the elements
        // arr[i] >= pivot and arr[j] <= pivot, but they're on wrong sides
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
/**
 * Quick Sort using Hoare Partition
 * 
 * Note: The recursive calls are different from Lomuto!
 * We recurse on [low, p] and [p+1, high], not [low, p-1] and [p+1, high]
 * This is because Hoare doesn't guarantee pivot is at position p
 */
function quickSortHoare(arr: number[], low: number, high: number): void {
    if (low < high) {
        const p = hoarePartition(arr, low, high);
        
        // IMPORTANT: Different from Lomuto!
        quickSortHoare(arr, low, p);      // Include p, not p-1
        quickSortHoare(arr, p + 1, high);
    }
}

Trace Through an Example:

Let's partition [8, 3, 7, 1, 5, 2, 6, 4] with pivot = 8 (first element).

Hoare Partition Trace: [8, 3, 7, 1, 5, 2, 6, 4], pivot = 8
Step	i	j	Action	Array State
Init	-1	8	Starting state	[8, 3, 7, 1, 5, 2, 6, 4]
1a	0	8	i++ until A[i]>=8: stop at i=0	[8, 3, 7, 1, 5, 2, 6, 4]
1b	0	7	j-- until A[j]<=8: stop at j=7	[8, 3, 7, 1, 5, 2, 6, 4]
1c	0	7	i<j: swap(0,7)	[4, 3, 7, 1, 5, 2, 6, 8]
2a	6	7	i++ until A[i]>=8: stop at i=7	[4, 3, 7, 1, 5, 2, 6, 8]
2b	7	6	j-- until A[j]<=8: stop at j=6	[4, 3, 7, 1, 5, 2, 6, 8]
2d	—	—	i>=j: return j=6	[4, 3, 7, 1, 5, 2, 6, 8]

Final Result: [4, 3, 7, 1, 5, 2, 6, 8] with partition point 6

Left partition: [4, 3, 7, 1, 5, 2, 6] — needs further sorting (contains 7 > 6, but that's fine, partition is [low..p])
Right partition: [8] — single element
Notice: The pivot 8 ended up at position 7, but we return j=6

Wait, elements aren't fully separated?

This is a key difference from Lomuto! Hoare's invariant is weaker:

A[low..j] ≤ pivot
A[j+1..high] ≥ pivot

The pivot value might appear in either partition. Both partitions still need sorting, and the algorithm is correct because:

Each partition is smaller than the original (unless all elements equal pivot)
Elements eventually reach correct positions through recursive partitioning

Hoare's Subtlety

Hoare partition is correct but subtle. The returned index j is NOT necessarily where the pivot ends up. It's simply a dividing line such that A[low..j] ≤ pivot and A[j+1..high] ≥ pivot. The pivot might be at any position in either partition. This is why you must recurse on [low, j] not [low, j-1].

Side-by-Side Comparison

Let's directly compare the two schemes across multiple dimensions to understand their tradeoffs.

Lomuto vs Hoare: Comprehensive Comparison
Aspect	Lomuto	Hoare
Inventor	Nico Lomuto	Tony Hoare (with Quick Sort, 1959)
Pointer movement	Single pointer, left to right	Two pointers, inward from both ends
Pivot position	Always at A[high] initially	Can be anywhere (typically A[low] or A[mid])
Pivot final position	Guaranteed at returned index	NOT guaranteed at returned index
Recursive call bounds	quickSort(low, p-1) and (p+1, high)	quickSort(low, p) and (p+1, high)
Average swaps	≈ n/2 on random data	≈ n/6 on random data
Comparisons	n-1 exactly	n-1 to n+1
Handling duplicates	All equals go to one side	Equals distributed between sides
Code complexity	Simpler, fewer edge cases	More complex, subtle termination
Common bugs	Off-by-one in final swap	Infinite loop with wrong pivot/bounds

Why Hoare Uses Fewer Swaps:

Consider what happens when partitioning a random array:

Lomuto: Every element ≤ pivot triggers a swap into the "small" region. With random data, about half the elements are ≤ pivot, so we perform ≈ n/2 swaps.

Hoare: We only swap when BOTH pointers find an element on the wrong side:

i finds element ≥ pivot (wrong side for left region)
j finds element ≤ pivot (wrong side for right region)
We swap this pair

With random data, this happens much less frequently. Analysis shows ≈ n/6 swaps on average — three times fewer than Lomuto.

This difference matters because swaps are expensive operations involving three memory accesses (read two elements, write two elements with temp storage or destructuring).

When to Use Lomuto

•Teaching and learning environments
•When code clarity is paramount
•When correctness is more important than speed
•Quick prototyping where performance isn't critical
•When debugging partition logic

When to Use Hoare

•Production systems where performance matters
•Large datasets where swap reduction is significant
•When combined with median-of-three pivot
•Standard library implementations
•When you're confident in correctness

Common Implementation Bugs and How to Avoid Them

Both partition schemes have subtle correctness requirements. Let's examine the most common bugs and how to avoid them.

Lomuto Common Bugs:

lomuto-bugs.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
// BUG 1: Wrong initialization of boundary variable
function buggyLomuto1(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low;  // BUG! Should be low - 1
    // This causes first element to be skipped or misclassified
    // ...
}
 
// BUG 2: Wrong loop bounds
function buggyLomuto2(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    for (let i = low; i <= high; i++) {  // BUG! Should be i < high
        // This processes the pivot itself, corrupting partition
        // ...
    }
}
 
// BUG 3: Wrong comparison operator
function buggyLomuto3(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    for (let i = low; i < high; i++) {
        if (arr[i] < pivot) {  // BUG! Should be <=
            // Equal elements all go right, causing worst-case on duplicates
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
    }
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    return j + 1;
}
 
// BUG 4: Wrong final swap
function buggyLomuto4(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    for (let i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
    }
    [arr[j], arr[high]] = [arr[high], arr[j]];  // BUG! Should be j+1
    return j;  // BUG! Should return j+1
}

Hoare Common Bugs:

hoare-bugs.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
// BUG 1: Using == instead of >= in termination check
function buggyHoare1(arr: number[], low: number, high: number): number {
    const pivot = arr[low];
    let i = low - 1, j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i == j) return j;  // BUG! Should be i >= j
        // When i and j cross without being equal, infinite loop or wrong result
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
// BUG 2: Wrong initial pointer values  
function buggyHoare2(arr: number[], low: number, high: number): number {
    const pivot = arr[low];
    let i = low, j = high;  // BUG! Should be low-1 and high+1
    // First iteration will skip first/last element
    while (true) {
        do { i++; } while (arr[i] < pivot);  // May go out of bounds
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
// BUG 3: Using wrong recursive call bounds
function buggyQuickSortHoare(arr: number[], low: number, high: number): void {
    if (low < high) {
        const p = hoarePartition(arr, low, high);
        buggyQuickSortHoare(arr, low, p - 1);  // BUG! Should be p, not p-1
        buggyQuickSortHoare(arr, p + 1, high);
    }
}
 
// BUG 4: Infinite loop with wrong pivot selection
function buggyHoare4(arr: number[], low: number, high: number): number {
    const pivot = arr[high];  // Using high as pivot with this logic can cause issues
    let i = low - 1, j = high + 1;  
    // If pivot is the minimum, j will never find element <= pivot before hitting low
    // Need careful handling or use low/mid as pivot with this pointer setup
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

Testing Partition Implementations

Always test partitions with: (1) single element [5], (2) two elements [5,3] and [3,5], (3) three elements with duplicates [3,3,3], (4) already sorted [1,2,3,4,5], (5) reverse sorted [5,4,3,2,1], (6) all elements equal to pivot. These cases expose most off-by-one and boundary bugs.

The Invariants in Detail

Understanding loop invariants is the key to implementing partition correctly. Let's formalize the invariants for both schemes.

Lomuto Invariant:

At the start of each iteration of the for loop (before processing element i):

Initialization (before loop): j = low - 1
- A[low..j] is empty (no elements)
- A[j+1..low-1] is empty (no elements)
- Invariant trivially satisfied
Maintenance (during loop): At iteration i:
- A[low..j] contains elements ≤ pivot from A[low..i-1]
- A[j+1..i-1] contains elements > pivot from A[low..i-1]
- After processing A[i]:
  - If A[i] ≤ pivot: j++, swap extends "small" region
  - If A[i] > pivot: no action, "large" region naturally expands
Termination (after loop): i = high
- A[low..j] contains all elements ≤ pivot from A[low..high-1]
- A[j+1..high-1] contains all elements > pivot
- A[high] is pivot
- Swap A[j+1] with A[high] places pivot in correct position

Hoare Invariant:

The invariant is more nuanced because we maintain regions from both ends:

Before each swap:
- A[low..i-1] contains elements < pivot
- A[j+1..high] contains elements > pivot
- The pointers i and j have found elements ≥ pivot and ≤ pivot respectively
After termination (i ≥ j):
- A[low..j] contains elements ≤ pivot
- A[j+1..high] contains elements ≥ pivot
- Note: the pivot value may appear in either partition

invariant-annotated.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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Lomuto with detailed invariant annotations
 */
function lomutoAnnotated(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    
    // INVARIANT: A[low..j] has elements ≤ pivot
    //            A[j+1..i-1] has elements > pivot
    // Initially: both regions are empty (j = low-1, i = low)
    
    for (let i = low; i < high; i++) {
        // Check invariant holds:
        // assert: forall k in [low..j]: A[k] <= pivot
        // assert: forall k in [j+1..i-1]: A[k] > pivot
        
        if (arr[i] <= pivot) {
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
            // A[j] now contains element <= pivot
            // Invariant maintained: "small" region extended
        }
        // else: A[i] > pivot, "large" region extended (j+1..i)
    }
    
    // After loop: i = high
    // A[low..j] = all elements ≤ pivot
    // A[j+1..high-1] = all elements > pivot  
    // A[high] = pivot
    
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    
    // Final state:
    // A[low..j] ≤ A[j+1] (pivot) ≤ A[j+2..high]
    
    return j + 1;
}
 
/**
 * Hoare with detailed invariant annotations
 */
function hoareAnnotated(arr: number[], low: number, high: number): number {
    const pivot = arr[low];
    let i = low - 1;
    let j = high + 1;
    
    while (true) {
        // Find rightmost element in left region that's >= pivot
        do { i++; } while (arr[i] < pivot);
        // Post: arr[i] >= pivot, and all arr[low..i-1] < pivot
        
        // Find leftmost element in right region that's <= pivot
        do { j--; } while (arr[j] > pivot);
        // Post: arr[j] <= pivot, and all arr[j+1..high] > pivot
        
        if (i >= j) {
            // INVARIANT at termination:
            // arr[low..j] ≤ pivot (because arr[low..i-1] < pivot and arr[j] <= pivot)
            // arr[j+1..high] ≥ pivot (because arr[j+1..high] > pivot, with possible exception at crossing)
            return j;
        }
        
        // Both i and j are valid and haven't crossed
        // arr[i] >= pivot but belongs in left (should be < pivot)
        // arr[j] <= pivot but belongs in right (should be > pivot)
        // Swap them to restore invariant progress
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

Performance Analysis

Let's analyze the performance of both partition schemes rigorously.

Comparison Count:

Both schemes perform Θ(n) comparisons per partition call:

Lomuto: Exactly n-1 comparisons (one per element except pivot)
Hoare: Between n-1 and n+1 comparisons (depends on when pointers cross)

The comparison counts are essentially identical in big-O terms.

Swap Count (the key difference):

This is where the schemes differ significantly.

Lomuto Swap Analysis:

Every element ≤ pivot triggers a swap. If k elements are ≤ pivot:

Number of swaps = k + 1 (k for elements, 1 for final pivot placement)

For random data where each element is equally likely to be ≤ pivot:

Expected k = (n-1)/2
Expected swaps = n/2 + 1 = Θ(n/2)

Worst case (all elements ≤ pivot): n swaps

Hoare Swap Analysis:

Swaps occur only when both pointers find an element on the "wrong" side. Analysis of random permutations shows:

Expected swaps ≈ n/6

This is 3x fewer swaps than Lomuto on average!

The intuition: Hoare swaps efficiently "fix" pairs of misplaced elements, while Lomuto swaps every "small" element into position one by one.

Partition Performance Summary (for n elements)
Metric	Lomuto	Hoare	Winner
Comparisons	n-1	n-1 to n+1	Tie
Expected swaps (random)	n/2	n/6	Hoare (3x better)
Worst-case swaps	n	n/2	Hoare (2x better)
Best-case swaps	1	0	Hoare
Cache behavior	Good	Excellent	Hoare (slightly)
Code simplicity	Simple	Complex	Lomuto
Correctness pitfalls	Few	Many	Lomuto

Real-World Benchmark Considerations:

While Hoare performs fewer swaps, the actual performance difference depends on:

Element size: For small elements (integers), swap overhead is minimal; comparison may dominate. For large structs, swap reduction matters more.
Comparison cost: If comparison involves string comparison or custom comparators, comparisons dominate and swap savings matter less.
Cache effects: Hoare's bidirectional scan may have different cache behavior than Lomuto's unidirectional scan, though both are generally cache-friendly.
Branch prediction: Modern CPUs predict branches. Lomuto has a single forward scan that may predict better than Hoare's pattern.

Empirical results: On most systems with integer or pointer elements, Hoare is 10-20% faster than Lomuto. The gap widens for larger elements.

Modern Optimizations

Production implementations often use hybrid approaches: Hoare partition with median-of-three pivot selection, switching to Insertion Sort for small subarrays, and using three-way partitioning when many duplicates are detected. The base algorithm matters less than these optimizations for achieving peak performance.

Choosing Between Schemes

Given the tradeoffs, how should you choose between Lomuto and Hoare? Here's a decision framework:

Choose Lomuto When:

Learning or teaching Quick Sort — Lomuto's single-scan approach with clear regions is easier to understand and verify.
Code maintainability matters more than peak performance — When others will read and modify your code, simpler is better.
Interview settings — Many interviewers expect Lomuto (from CLRS familiarity). It's easier to write correctly under pressure.
One-off scripts or prototypes — The performance difference won't matter for small or infrequent use.

Choose Hoare When:

Performance is critical — The 3x swap reduction adds up on large datasets.
Standard library implementations — If you're writing a library sort, use Hoare (or its variants).
Large elements — Swapping large structs or objects benefits more from swap reduction.
You're confident in the implementation — Only use Hoare if you understand its subtleties.

Special Considerations

•Many duplicates: Neither basic scheme handles duplicates well. Consider three-way partitioning (Dutch National Flag) for arrays with many equal elements.
•Nearly sorted data: With fixed pivots, both degrade to O(n²). Use median-of-three or random pivot selection with either scheme.
•Security-sensitive contexts: With deterministic partitioning, adversarial inputs can cause O(n²). Use randomization.
•Stability required: Neither scheme is stable. If you need stability, use Merge Sort or Timsort instead.

The Best of Both Worlds:

Many production implementations combine ideas from both schemes:

1. Use median-of-three for pivot selection
2. Use Hoare's bidirectional scan for efficiency
3. Switch to Insertion Sort for small subarrays
4. Detect excessive recursion depth and switch to Heap Sort (Introsort)
5. Use three-way partitioning when duplicates are detected

This hybrid approach inherits Hoare's efficiency, protects against worst-case inputs, and handles edge cases gracefully.

Summary: Lomuto vs Hoare

We've thoroughly examined the two classic partition schemes. Here are the essential takeaways:

Key Takeaways

•Lomuto: Simplicity — Single scan, clear invariant, pivot ends at returned index. Preferred for learning and interviews.
•Hoare: Efficiency — Bidirectional scan, 3x fewer swaps on average. Pivot may NOT be at returned index. Preferred for production.
•Different recursive call bounds — Lomuto: quickSort(low, p-1) and (p+1, high). Hoare: quickSort(low, p) and (p+1, high). Getting this wrong causes bugs.
•Both need help with variants — Neither handles duplicates or sorted inputs well without additional strategies (three-way partitioning, random pivots).
•Know both schemes — Understanding both makes you flexible; you can implement the appropriate one for any context.
•Production implementations are hybrids — They combine the best ideas from both schemes plus additional optimizations.

What's Next:

Now that we understand the mechanics of partitioning, we need to analyze Quick Sort's time complexity rigorously. Why is it O(n log n) on average but O(n²) in the worst case? How do different pivot strategies affect the constants? This analysis is the subject of our next page.

Page Complete

You can now implement both Lomuto and Hoare partition schemes, understand their invariants, and choose the appropriate one for your context. You understand why Hoare is more efficient (fewer swaps) but more subtle to implement correctly. This knowledge prepares you for implementing production-quality Quick Sort.

Lomuto vs Hoare Partition Schemes

Two Paths to the Same Goal

What You Will Learn

Lomuto Partition Scheme

Key Characteristics:

Pivot is always the last element (A[high])
Single scan from left to right
Maintains boundary j: everything in A[low..j] is ≤ pivot
Returns the pivot's final position after placing it

The Invariant:

At any point during the scan, the array is divided into four regions:

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

As we scan, each element is classified and moved to the appropriate region.

lomuto-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
56
57
58
59
60
61
62
63
/**
 * Lomuto Partition Scheme
 * 
 * Algorithm:
 * 1. Select the last element as pivot
 * 2. Initialize boundary j = low - 1 (nothing in "small" region yet)
 * 3. Scan elements from low to high-1
 *    - If element ≤ pivot: expand "small" region and swap element in
 *    - If element > pivot: "large" region naturally expands
 * 4. Place pivot between the two regions
 * 5. Return pivot's position
 * 
 * @param arr - The array to partition
 * @param low - Starting index (inclusive)
 * @param high - Ending index (inclusive), arr[high] is the pivot
 * @returns The final index of the pivot
 */
function lomutoPartition(arr: number[], low: number, high: number): number {
    const pivot = arr[high]; // Step 1: Last element is pivot
    
    let j = low - 1; // Step 2: j is the boundary of "small" region
                     // A[low..j] will contain elements ≤ pivot
                     // Initially empty (j < low)
    
    // Step 3: Scan through all elements except pivot
    for (let i = low; i < high; i++) {
        // INVARIANT at this point:
        // - A[low..j] has elements ≤ pivot
        // - A[j+1..i-1] has elements > pivot
        // - A[i..high-1] is unprocessed
        // - A[high] is pivot
        
        if (arr[i] <= pivot) {
            // This element belongs in the "small" region
            j++; // Expand the "small" region
            
            // Swap arr[i] into the "small" region
            // arr[j] was the first element of "large" region (or unprocessed)
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
        // If arr[i] > pivot, no action needed
        // The "large" region naturally expands to include it
    }
    
    // Step 4: Place pivot in its final position
    // The pivot should go right after the "small" region
    // That position is j + 1
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    
    // Step 5: Return pivot's final position
    return j + 1;
}
 
/**
 * Complete Quick Sort using Lomuto Partition
 */
function quickSortLomuto(arr: number[], low: number, high: number): void {
    if (low < high) {
        const pivotIndex = lomutoPartition(arr, low, high);
        quickSortLomuto(arr, low, pivotIndex - 1);
        quickSortLomuto(arr, pivotIndex + 1, high);
    }
}

Trace Through an Example:

Let's partition [8, 3, 7, 1, 5, 2, 6, 4] with pivot = 4 (last element).

Lomuto Partition Trace: [8, 3, 7, 1, 5, 2, 6, 4], pivot = 4
Step	i	j	A[i]	A[i] ≤ 4?	Action	Array State
Init	—	-1	—	—	—	[8, 3, 7, 1, 5, 2, 6, 4]
1	0	-1	8	No	Skip	[8, 3, 7, 1, 5, 2, 6, 4]
2	1	-1	3	Yes	j++, swap(0,1)	[3, 8, 7, 1, 5, 2, 6, 4]
3	2	0	7	No	Skip	[3, 8, 7, 1, 5, 2, 6, 4]
4	3	0	1	Yes	j++, swap(1,3)	[3, 1, 7, 8, 5, 2, 6, 4]
5	4	1	5	No	Skip	[3, 1, 7, 8, 5, 2, 6, 4]
6	5	1	2	Yes	j++, swap(2,5)	[3, 1, 2, 8, 5, 7, 6, 4]
7	6	2	6	No	Skip	[3, 1, 2, 8, 5, 7, 6, 4]
Final	—	2	—	—	swap(3,7)	[3, 1, 2, 4, 5, 7, 6, 8]

Final Result: [3, 1, 2, 4, 5, 7, 6, 8]

Pivot index returned: 3
Left partition: [3, 1, 2] — all ≤ 4 ✓
Right partition: [5, 7, 6, 8] — all > 4 ✓
Pivot 4 is in its final sorted position ✓

Analysis of Lomuto:

Comparisons: Exactly n-1 comparisons (one per element except pivot)
Swaps: O(n) in the worst case (when all elements < pivot)
Simplicity: Very straightforward invariant and logic
Stability: Not stable (swaps can change relative order of equal elements)

Lomuto's Weakness: Duplicates

Hoare Partition Scheme

Key Characteristics:

Uses two pointers: i starts from left, j starts from right
Pointers move toward each other until they cross
Swaps pairs of misplaced elements
Pivot can be any element (often first or middle)
Returns a partition point — but the pivot may NOT be at this position

This means the recursive calls in Quick Sort with Hoare partition are slightly different:

QuickSort(A, low, p)     // NOT p-1
QuickSort(A, p+1, high)

hoare-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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Hoare Partition Scheme
 * 
 * Algorithm:
 * 1. Select a pivot (often first or middle element)
 * 2. Initialize two pointers: i at low-1, j at high+1
 * 3. Loop:
 *    a. Move i right until A[i] >= pivot
 *    b. Move j left until A[j] <= pivot  
 *    c. If i < j: swap A[i] and A[j]
 *    d. If i >= j: return j as the partition point
 * 
 * @param arr - The array to partition
 * @param low - Starting index (inclusive)
 * @param high - Ending index (inclusive)
 * @returns The partition point p where A[low..p] ≤ pivot, A[p+1..high] ≥ pivot
 */
function hoarePartition(arr: number[], low: number, high: number): number {
    // Step 1: Select pivot (using first element)
    // Using middle element is also common and protects against sorted inputs
    const pivot = arr[low];
    // Alternative: const pivot = arr[Math.floor((low + high) / 2)];
    
    // Step 2: Initialize pointers outside the array bounds
    // They will be moved before first access
    let i = low - 1;
    let j = high + 1;
    
    // Step 3: Main loop
    while (true) {
        // Step 3a: Move i right, find element >= pivot
        do {
            i++;
        } while (arr[i] < pivot);
        
        // Step 3b: Move j left, find element <= pivot
        do {
            j--;
        } while (arr[j] > pivot);
        
        // Step 3c & 3d: Check if pointers crossed
        if (i >= j) {
            // Pointers have crossed or met
            // j is the partition point
            return j;
        }
        
        // Pointers haven't crossed: swap the elements
        // arr[i] >= pivot and arr[j] <= pivot, but they're on wrong sides
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
/**
 * Quick Sort using Hoare Partition
 * 
 * Note: The recursive calls are different from Lomuto!
 * We recurse on [low, p] and [p+1, high], not [low, p-1] and [p+1, high]
 * This is because Hoare doesn't guarantee pivot is at position p
 */
function quickSortHoare(arr: number[], low: number, high: number): void {
    if (low < high) {
        const p = hoarePartition(arr, low, high);
        
        // IMPORTANT: Different from Lomuto!
        quickSortHoare(arr, low, p);      // Include p, not p-1
        quickSortHoare(arr, p + 1, high);
    }
}

Trace Through an Example:

Let's partition [8, 3, 7, 1, 5, 2, 6, 4] with pivot = 8 (first element).

Hoare Partition Trace: [8, 3, 7, 1, 5, 2, 6, 4], pivot = 8
Step	i	j	Action	Array State
Init	-1	8	Starting state	[8, 3, 7, 1, 5, 2, 6, 4]
1a	0	8	i++ until A[i]>=8: stop at i=0	[8, 3, 7, 1, 5, 2, 6, 4]
1b	0	7	j-- until A[j]<=8: stop at j=7	[8, 3, 7, 1, 5, 2, 6, 4]
1c	0	7	i<j: swap(0,7)	[4, 3, 7, 1, 5, 2, 6, 8]
2a	6	7	i++ until A[i]>=8: stop at i=7	[4, 3, 7, 1, 5, 2, 6, 8]
2b	7	6	j-- until A[j]<=8: stop at j=6	[4, 3, 7, 1, 5, 2, 6, 8]
2d	—	—	i>=j: return j=6	[4, 3, 7, 1, 5, 2, 6, 8]

Final Result: [4, 3, 7, 1, 5, 2, 6, 8] with partition point 6

Left partition: [4, 3, 7, 1, 5, 2, 6] — needs further sorting (contains 7 > 6, but that's fine, partition is [low..p])
Right partition: [8] — single element
Notice: The pivot 8 ended up at position 7, but we return j=6

Wait, elements aren't fully separated?

This is a key difference from Lomuto! Hoare's invariant is weaker:

A[low..j] ≤ pivot
A[j+1..high] ≥ pivot

The pivot value might appear in either partition. Both partitions still need sorting, and the algorithm is correct because:

Each partition is smaller than the original (unless all elements equal pivot)
Elements eventually reach correct positions through recursive partitioning

Hoare's Subtlety

Side-by-Side Comparison

Let's directly compare the two schemes across multiple dimensions to understand their tradeoffs.

Lomuto vs Hoare: Comprehensive Comparison
Aspect	Lomuto	Hoare
Inventor	Nico Lomuto	Tony Hoare (with Quick Sort, 1959)
Pointer movement	Single pointer, left to right	Two pointers, inward from both ends
Pivot position	Always at A[high] initially	Can be anywhere (typically A[low] or A[mid])
Pivot final position	Guaranteed at returned index	NOT guaranteed at returned index
Recursive call bounds	quickSort(low, p-1) and (p+1, high)	quickSort(low, p) and (p+1, high)
Average swaps	≈ n/2 on random data	≈ n/6 on random data
Comparisons	n-1 exactly	n-1 to n+1
Handling duplicates	All equals go to one side	Equals distributed between sides
Code complexity	Simpler, fewer edge cases	More complex, subtle termination
Common bugs	Off-by-one in final swap	Infinite loop with wrong pivot/bounds

Why Hoare Uses Fewer Swaps:

Consider what happens when partitioning a random array:

Lomuto: Every element ≤ pivot triggers a swap into the "small" region. With random data, about half the elements are ≤ pivot, so we perform ≈ n/2 swaps.

Hoare: We only swap when BOTH pointers find an element on the wrong side:

i finds element ≥ pivot (wrong side for left region)
j finds element ≤ pivot (wrong side for right region)
We swap this pair

With random data, this happens much less frequently. Analysis shows ≈ n/6 swaps on average — three times fewer than Lomuto.

This difference matters because swaps are expensive operations involving three memory accesses (read two elements, write two elements with temp storage or destructuring).

When to Use Lomuto

•Teaching and learning environments
•When code clarity is paramount
•When correctness is more important than speed
•Quick prototyping where performance isn't critical
•When debugging partition logic

When to Use Hoare

•Production systems where performance matters
•Large datasets where swap reduction is significant
•When combined with median-of-three pivot
•Standard library implementations
•When you're confident in correctness

Common Implementation Bugs and How to Avoid Them

Both partition schemes have subtle correctness requirements. Let's examine the most common bugs and how to avoid them.

Lomuto Common Bugs:

lomuto-bugs.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
// BUG 1: Wrong initialization of boundary variable
function buggyLomuto1(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low;  // BUG! Should be low - 1
    // This causes first element to be skipped or misclassified
    // ...
}
 
// BUG 2: Wrong loop bounds
function buggyLomuto2(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    for (let i = low; i <= high; i++) {  // BUG! Should be i < high
        // This processes the pivot itself, corrupting partition
        // ...
    }
}
 
// BUG 3: Wrong comparison operator
function buggyLomuto3(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    for (let i = low; i < high; i++) {
        if (arr[i] < pivot) {  // BUG! Should be <=
            // Equal elements all go right, causing worst-case on duplicates
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
    }
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    return j + 1;
}
 
// BUG 4: Wrong final swap
function buggyLomuto4(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    for (let i = low; i < high; i++) {
        if (arr[i] <= pivot) {
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
        }
    }
    [arr[j], arr[high]] = [arr[high], arr[j]];  // BUG! Should be j+1
    return j;  // BUG! Should return j+1
}

Hoare Common Bugs:

hoare-bugs.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
// BUG 1: Using == instead of >= in termination check
function buggyHoare1(arr: number[], low: number, high: number): number {
    const pivot = arr[low];
    let i = low - 1, j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i == j) return j;  // BUG! Should be i >= j
        // When i and j cross without being equal, infinite loop or wrong result
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
// BUG 2: Wrong initial pointer values  
function buggyHoare2(arr: number[], low: number, high: number): number {
    const pivot = arr[low];
    let i = low, j = high;  // BUG! Should be low-1 and high+1
    // First iteration will skip first/last element
    while (true) {
        do { i++; } while (arr[i] < pivot);  // May go out of bounds
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
// BUG 3: Using wrong recursive call bounds
function buggyQuickSortHoare(arr: number[], low: number, high: number): void {
    if (low < high) {
        const p = hoarePartition(arr, low, high);
        buggyQuickSortHoare(arr, low, p - 1);  // BUG! Should be p, not p-1
        buggyQuickSortHoare(arr, p + 1, high);
    }
}
 
// BUG 4: Infinite loop with wrong pivot selection
function buggyHoare4(arr: number[], low: number, high: number): number {
    const pivot = arr[high];  // Using high as pivot with this logic can cause issues
    let i = low - 1, j = high + 1;  
    // If pivot is the minimum, j will never find element <= pivot before hitting low
    // Need careful handling or use low/mid as pivot with this pointer setup
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

Testing Partition Implementations

The Invariants in Detail

Understanding loop invariants is the key to implementing partition correctly. Let's formalize the invariants for both schemes.

Lomuto Invariant:

At the start of each iteration of the for loop (before processing element i):

Initialization (before loop): j = low - 1
- A[low..j] is empty (no elements)
- A[j+1..low-1] is empty (no elements)
- Invariant trivially satisfied
Maintenance (during loop): At iteration i:
- A[low..j] contains elements ≤ pivot from A[low..i-1]
- A[j+1..i-1] contains elements > pivot from A[low..i-1]
- After processing A[i]:
  - If A[i] ≤ pivot: j++, swap extends "small" region
  - If A[i] > pivot: no action, "large" region naturally expands
Termination (after loop): i = high
- A[low..j] contains all elements ≤ pivot from A[low..high-1]
- A[j+1..high-1] contains all elements > pivot
- A[high] is pivot
- Swap A[j+1] with A[high] places pivot in correct position

Hoare Invariant:

The invariant is more nuanced because we maintain regions from both ends:

Before each swap:
- A[low..i-1] contains elements < pivot
- A[j+1..high] contains elements > pivot
- The pointers i and j have found elements ≥ pivot and ≤ pivot respectively
After termination (i ≥ j):
- A[low..j] contains elements ≤ pivot
- A[j+1..high] contains elements ≥ pivot
- Note: the pivot value may appear in either partition

invariant-annotated.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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Lomuto with detailed invariant annotations
 */
function lomutoAnnotated(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let j = low - 1;
    
    // INVARIANT: A[low..j] has elements ≤ pivot
    //            A[j+1..i-1] has elements > pivot
    // Initially: both regions are empty (j = low-1, i = low)
    
    for (let i = low; i < high; i++) {
        // Check invariant holds:
        // assert: forall k in [low..j]: A[k] <= pivot
        // assert: forall k in [j+1..i-1]: A[k] > pivot
        
        if (arr[i] <= pivot) {
            j++;
            [arr[j], arr[i]] = [arr[i], arr[j]];
            // A[j] now contains element <= pivot
            // Invariant maintained: "small" region extended
        }
        // else: A[i] > pivot, "large" region extended (j+1..i)
    }
    
    // After loop: i = high
    // A[low..j] = all elements ≤ pivot
    // A[j+1..high-1] = all elements > pivot  
    // A[high] = pivot
    
    [arr[j + 1], arr[high]] = [arr[high], arr[j + 1]];
    
    // Final state:
    // A[low..j] ≤ A[j+1] (pivot) ≤ A[j+2..high]
    
    return j + 1;
}
 
/**
 * Hoare with detailed invariant annotations
 */
function hoareAnnotated(arr: number[], low: number, high: number): number {
    const pivot = arr[low];
    let i = low - 1;
    let j = high + 1;
    
    while (true) {
        // Find rightmost element in left region that's >= pivot
        do { i++; } while (arr[i] < pivot);
        // Post: arr[i] >= pivot, and all arr[low..i-1] < pivot
        
        // Find leftmost element in right region that's <= pivot
        do { j--; } while (arr[j] > pivot);
        // Post: arr[j] <= pivot, and all arr[j+1..high] > pivot
        
        if (i >= j) {
            // INVARIANT at termination:
            // arr[low..j] ≤ pivot (because arr[low..i-1] < pivot and arr[j] <= pivot)
            // arr[j+1..high] ≥ pivot (because arr[j+1..high] > pivot, with possible exception at crossing)
            return j;
        }
        
        // Both i and j are valid and haven't crossed
        // arr[i] >= pivot but belongs in left (should be < pivot)
        // arr[j] <= pivot but belongs in right (should be > pivot)
        // Swap them to restore invariant progress
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

Performance Analysis

Let's analyze the performance of both partition schemes rigorously.

Comparison Count:

Both schemes perform Θ(n) comparisons per partition call:

Lomuto: Exactly n-1 comparisons (one per element except pivot)
Hoare: Between n-1 and n+1 comparisons (depends on when pointers cross)

The comparison counts are essentially identical in big-O terms.

Swap Count (the key difference):

This is where the schemes differ significantly.

Lomuto Swap Analysis:

Every element ≤ pivot triggers a swap. If k elements are ≤ pivot:

Number of swaps = k + 1 (k for elements, 1 for final pivot placement)

For random data where each element is equally likely to be ≤ pivot:

Expected k = (n-1)/2
Expected swaps = n/2 + 1 = Θ(n/2)

Worst case (all elements ≤ pivot): n swaps

Hoare Swap Analysis:

Swaps occur only when both pointers find an element on the "wrong" side. Analysis of random permutations shows:

Expected swaps ≈ n/6

This is 3x fewer swaps than Lomuto on average!

The intuition: Hoare swaps efficiently "fix" pairs of misplaced elements, while Lomuto swaps every "small" element into position one by one.

Partition Performance Summary (for n elements)
Metric	Lomuto	Hoare	Winner
Comparisons	n-1	n-1 to n+1	Tie
Expected swaps (random)	n/2	n/6	Hoare (3x better)
Worst-case swaps	n	n/2	Hoare (2x better)
Best-case swaps	1	0	Hoare
Cache behavior	Good	Excellent	Hoare (slightly)
Code simplicity	Simple	Complex	Lomuto
Correctness pitfalls	Few	Many	Lomuto

Real-World Benchmark Considerations:

While Hoare performs fewer swaps, the actual performance difference depends on:

Element size: For small elements (integers), swap overhead is minimal; comparison may dominate. For large structs, swap reduction matters more.
Comparison cost: If comparison involves string comparison or custom comparators, comparisons dominate and swap savings matter less.
Cache effects: Hoare's bidirectional scan may have different cache behavior than Lomuto's unidirectional scan, though both are generally cache-friendly.
Branch prediction: Modern CPUs predict branches. Lomuto has a single forward scan that may predict better than Hoare's pattern.

Empirical results: On most systems with integer or pointer elements, Hoare is 10-20% faster than Lomuto. The gap widens for larger elements.

Modern Optimizations

Choosing Between Schemes

Given the tradeoffs, how should you choose between Lomuto and Hoare? Here's a decision framework:

Choose Lomuto When:

Learning or teaching Quick Sort — Lomuto's single-scan approach with clear regions is easier to understand and verify.
Code maintainability matters more than peak performance — When others will read and modify your code, simpler is better.
Interview settings — Many interviewers expect Lomuto (from CLRS familiarity). It's easier to write correctly under pressure.
One-off scripts or prototypes — The performance difference won't matter for small or infrequent use.

Choose Hoare When:

Performance is critical — The 3x swap reduction adds up on large datasets.
Standard library implementations — If you're writing a library sort, use Hoare (or its variants).
Large elements — Swapping large structs or objects benefits more from swap reduction.
You're confident in the implementation — Only use Hoare if you understand its subtleties.

Special Considerations

•Many duplicates: Neither basic scheme handles duplicates well. Consider three-way partitioning (Dutch National Flag) for arrays with many equal elements.
•Nearly sorted data: With fixed pivots, both degrade to O(n²). Use median-of-three or random pivot selection with either scheme.
•Security-sensitive contexts: With deterministic partitioning, adversarial inputs can cause O(n²). Use randomization.
•Stability required: Neither scheme is stable. If you need stability, use Merge Sort or Timsort instead.

The Best of Both Worlds:

Many production implementations combine ideas from both schemes:

1. Use median-of-three for pivot selection
2. Use Hoare's bidirectional scan for efficiency
3. Switch to Insertion Sort for small subarrays
4. Detect excessive recursion depth and switch to Heap Sort (Introsort)
5. Use three-way partitioning when duplicates are detected

This hybrid approach inherits Hoare's efficiency, protects against worst-case inputs, and handles edge cases gracefully.

Summary: Lomuto vs Hoare

We've thoroughly examined the two classic partition schemes. Here are the essential takeaways:

Key Takeaways

•Lomuto: Simplicity — Single scan, clear invariant, pivot ends at returned index. Preferred for learning and interviews.
•Hoare: Efficiency — Bidirectional scan, 3x fewer swaps on average. Pivot may NOT be at returned index. Preferred for production.
•Different recursive call bounds — Lomuto: quickSort(low, p-1) and (p+1, high). Hoare: quickSort(low, p) and (p+1, high). Getting this wrong causes bugs.
•Both need help with variants — Neither handles duplicates or sorted inputs well without additional strategies (three-way partitioning, random pivots).
•Know both schemes — Understanding both makes you flexible; you can implement the appropriate one for any context.
•Production implementations are hybrids — They combine the best ideas from both schemes plus additional optimizations.

What's Next:

Page Complete