Quick Sort: Lomuto vs Hoare Partitioning & Pivot Strategies0%
Binary Tree Traversals: DFS (Pre, In, Post) & BFS Level-Order

Quick Sort: Lomuto vs Hoare Partitioning & Pivot Strategies

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Quick Sort: Lomuto vs Hoare Partitioning & Pivot Strategies

Quick Sort is an in-place divide-and-conquer sorting algorithm. In practical benchmarks, Quick Sort is typically 2x to 3x faster than Merge Sort and Heap Sort due to excellent CPU hardware cache locality and minimal memory movement.

1. Real-World Analogy: Sorting Students by Height Around a Reference

Imagine a gym teacher organizing 30 students by height:

  • The teacher picks one student (say, Alex) to stand in the center as the Pivot.
  • The teacher instructs: "Anyone shorter than Alex, move to his left. Anyone taller than Alex, move to his right."
  • Notice: Alex is now standing at his exact final sorted position forever!
  • The teacher repeats the exact same instruction recursively for the group on the left and the group on the right.

2. The Two Famous Partitioning Schemes

1. Lomuto Partition Scheme (Simpler to Understand)

  • The Pivot is chosen as the last element arr[high].
  • A slow pointer i maintains the boundary of elements smaller than the pivot.
  • A fast pointer j scans from low to high - 1.
  • When arr[j] <= pivot, increment i and swap arr[i] with arr[j].

2. Hoare Partition Scheme (Original & More Efficient)

  • Two pointers start at the outer ends (low - 1 and high + 1) and advance inward toward each other.
  • Makes approximately three times fewer swaps on average than Lomuto!

3. The Pivot Selection Trap ($O(n^2)$ Worst-Case)

If you always choose the first or last element as the pivot:

  • If the input array is already sorted or reverse sorted, the pivot produces a degenerate partition of size $0$ and $n - 1$.
  • The recursion tree degenerates from a balanced tree ($\log n$) into a linked list ($n$), resulting in worst-case $O(n^2)$ quadratic time!

The Remedy: Randomized Pivot or Median-of-Three

Pick three candidates (first, middle, last), find their mathematical median, and swap it to the pivot position. This guarantees balanced $O(n \log n)$ partitions in production!

4. Multi-Language Implementations: Quick Sort (Lomuto Partition)

Python 3:

Python
import random
 
def quick_sort(arr: list[int], low: int = 0, high: int = None) -> None:
if high is None:
high = len(arr) - 1
if low < high:
# Partition the array and get pivot index
pivot_index = randomized_partition(arr, low, high)
# Recursively sort elements before and after partition
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
 
def randomized_partition(arr: list[int], low: int, high: int) -> int:
rand_idx = random.randint(low, high)
arr[rand_idx], arr[high] = arr[high], arr[rand_idx] # Swap random to end
return lomuto_partition(arr, low, high)
 
def lomuto_partition(arr: list[int], low: int, high: int) -> int:
pivot = arr[high]
i = low - 1 # Boundary of elements <= pivot
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# Place pivot in its correct final position
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

Modern JavaScript / TypeScript:

TypeScript
export function quickSort(arr: number[], low: number = 0, high: number = arr.length - 1): void {
if (low < high) {
const pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, high);
}
}
 
function partition(arr: number[], low: number, high: number): number {
const pivot = arr[high];
let i = low - 1;
 
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
 
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}

5. Trace Table: Partitioning [10, 80, 30, 90, 40, 50, 70] (Pivot = 70)

jarr[j]arr[j] <= 70?iSwap ActionArray State
Init---1None[10, 80, 30, 90, 40, 50, 70]
010Yes0Swap arr[0] with arr[0][10, 80, 30, 90, 40, 50, 70]
180No0None[10, 80, 30, 90, 40, 50, 70]
230Yes1Swap arr[1] (80) with arr[2] (30)[10, 30, 80, 90, 40, 50, 70]
390No1None[10, 30, 80, 90, 40, 50, 70]
440Yes2Swap arr[2] (80) with arr[4] (40)[10, 30, 40, 90, 80, 50, 70]
550Yes3Swap arr[3] (90) with arr[5] (50)[10, 30, 40, 50, 80, 90, 70]
Final---Swap arr[4] (80) with pivot 70[10, 30, 40, 50, 70, 90, 80]

Pivot 70 is placed at index 4! All items to its left are $< 70$, all to its right are $> 70$.

Interactive Quiz

Multiple Choice Questions

Question 1
What is the average-case time complexity of Quick Sort?
Question 2
Under what input condition does naive Quick Sort (picking the first or last element as pivot) degrade to worst-case $O(n^2)$ time?
Question 3
How does "Randomized Quick Sort" mitigate the worst-case $O(n^2)$ scenario?
Question 4
Is standard in-place Quick Sort a "Stable" sorting algorithm?
Question 5
Why is Quick Sort faster in practical machine benchmarks than Merge Sort, even though both share $O(n \log n)$ average complexity?
Next Lesson

Binary Tree Traversals: DFS (Pre, In, Post) & BFS Level-Order

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Merge Sort: Divide-and-Conquer Paradigm & Stability AnalysisBinary Tree Traversals: DFS (Pre, In, Post) & BFS Level-Order

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext