Quick Sort Algorithm - Complete Guide with 5 Partition Variants

Overview

Quick Sort is one of the most efficient and widely used sorting algorithms. It uses a divide-and-conquer strategy: select a pivot element, partition the array so that smaller elements go left and larger go right, then recursively sort the partitions.

While the basic idea is simple, the way we choose the pivot and partition the array greatly impacts performance. This page explores 5 popular variants, each solving specific problems or optimizing for different scenarios.

---

Variant Comparison

Variant	Key Idea	Avg / Worst	Duplicates	Sorted Input	Use Case
Lomuto	Single pointer, last element as pivot	O(n log n) / O(n²)	⚠️ Poor	⚠️ Poor	Teaching, simple cases
Hoare	Two pointers from both ends	O(n log n) / O(n²)	✓ Better	✓ Fair	General purpose
Three-Way	Three regions: <, =, >	O(n log n) / O(n²)	✅ Excellent	✓ Good	Many duplicates
Median-of-Three	Pick median of first/mid/last	O(n log n) / O(n²)*	✓ Good	✅ Excellent	Sorted/reverse inputs
Dual-Pivot	Two pivots, three partitions	O(n log n) / O(n²)	✓ Good	✓ Good	JDK’s Arrays.sort()

* Worst case probability significantly reduced

---

1. Lomuto Partition

The textbook-standard partition scheme

💡 How It Works

Lomuto partition uses the last element as pivot and maintains a single pointer i that tracks the boundary between elements less than the pivot and those greater than or equal to it.

📝 Algorithm Steps

1. pivot ← array[right]
2. i ← left - 1  // boundary for smaller elements
3. FOR j FROM left TO right-1:
   └─ IF array[j] < pivot:
        i++
        SWAP array[i] ↔ array[j]
4. SWAP array[i+1] ↔ array[right]  // place pivot
5. RETURN i+1  // pivot's final position

💻 Implementation

JavaScriptJavaPython

Loading...

✅ Problem It Solves

Provides a straightforward, easy-to-understand partition that’s perfect for teaching and simple implementations.

⚠️ Weakness

When the array has many duplicate values, Lomuto degenerates to O(n²) because equal elements all go to one side, creating unbalanced partitions.

🎮 Interactive Visualization

Watch how the i pointer expands the “less than pivot” region as j scans the array.

---

2. Hoare Partition

The original quicksort partition by Tony Hoare

💡 How It Works

Hoare partition uses two pointers starting from opposite ends of the array. The left pointer finds elements ≥ pivot, the right pointer finds elements ≤ pivot, then they swap. This continues until the pointers cross.

📝 Algorithm Steps

1. pivot ← array[left]
2. i ← left - 1,  j ← right + 1
3. LOOP:
   └─ MOVE i → until array[i] ≥ pivot
   └─ MOVE j ← until array[j] ≤ pivot
   └─ IF i ≥ j: BREAK, RETURN j
   └─ SWAP array[i] ↔ array[j]
4. RETURN j  // partition point

💻 Implementation

JavaScriptJavaPython

Loading...

✅ Problem It Solves

Performs ~3× fewer swaps than Lomuto on average. The two-pointer approach is more efficient because elements naturally migrate toward their correct sides.

🔄 Key Difference from Lomuto

The pivot doesn’t end up at a fixed position after partitioning. Instead, we get a partition point j where elements left of j are ≤ pivot and elements right of j+1 are ≥ pivot.

🎮 Interactive Visualization

Watch the two pointers i and j converge from opposite ends, swapping misplaced elements.

---

3. Three-Way Partition (DNF)

Dutch National Flag algorithm for handling duplicates

💡 How It Works

Three-way partition divides the array into three regions:

• Elements less than pivot
• Elements equal to pivot
• Elements greater than pivot

This is also known as the Dutch National Flag (DNF) algorithm, named after Dijkstra’s solution for sorting the three colors of the Dutch flag.

📝 Algorithm Steps

1. lt ← left,  i ← left + 1,  gt ← right
2. pivot ← array[left]
3. WHILE i ≤ gt:
   ├─ IF array[i] < pivot:
   │    SWAP array[lt] ↔ array[i], lt++, i++
   ├─ ELIF array[i] > pivot:
   │    SWAP array[i] ↔ array[gt], gt--
   └─ ELSE: i++
4. RECURSE on [left, lt-1] and [gt+1, right]

💻 Implementation

JavaScriptJavaPython

Loading...

✅ Problem It Solves

Achieves O(n) time when all elements are equal! By grouping duplicates together, we avoid recursing into regions of identical values, making it ideal for arrays with many repeated values.

🇳🇱 Why “Dutch National Flag”?

Dijkstra posed the problem of sorting an array of three distinct values (like the 🔴 red, ⚪ white, and 🔵 blue stripes of the Dutch flag) in linear time with constant space. This partition scheme is the solution, treating values as <pivot, =pivot, >pivot.

🎮 Interactive Visualization

Watch how lt, i, and gt pointers maintain three distinct regions as elements are classified.

---

4. Median-of-Three

Smart pivot selection to avoid worst cases

💡 How It Works

Instead of blindly picking the first or last element as pivot (which causes O(n²) on sorted arrays), median-of-three examines the first, middle, and last elements, choosing the median value as pivot.

📝 Algorithm Steps

1. COMPARE array[left], array[mid], array[right]
2. SORT these three elements in place
3. pivot ← array[mid]  // the median
4. PROCEED with standard partitioning

💻 Implementation

JavaScriptJavaPython

Loading...

✅ Problem It Solves

Sorted or nearly-sorted arrays are the worst case for basic quicksort. Median-of-three dramatically reduces the probability of choosing an extreme pivot, ensuring more balanced partitions.

🏭 Real-World Usage

This technique is used in many standard library implementations (like C++‘s std::sort) combined with other optimizations.

🎮 Interactive Visualization

Observe how the algorithm first compares three candidates (first, middle, last) to find the median before partitioning.

---

5. Dual-Pivot

JDK’s Arrays.sort() algorithm with two pivots

💡 How It Works

Dual-pivot quicksort uses two pivots (P1 ≤ P2) to partition the array into three regions:

• Elements < P1 (left region)
• Elements between P1 and P2 (middle region)
• Elements > P2 (right region)

This was invented by Vladimir Yaroslavskiy and adopted by Java’s Arrays.sort() for primitive types.

📝 Algorithm Steps

1. ENSURE array[left] ≤ array[right]; else SWAP
2. P1 ← array[left],  P2 ← array[right]
3. lt ← left + 1,  k ← left + 1,  gt ← right - 1
4. WHILE k ≤ gt:
   ├─ IF array[k] < P1: SWAP to left, lt++, k++
   ├─ ELIF array[k] > P2: SWAP to right, gt--
   └─ ELSE: k++  // middle region
5. PLACE pivots in final positions
6. RECURSE on three partitions

💻 Implementation

JavaScriptJavaPython

Loading...

✅ Problem It Solves

Dual-pivot quicksort has better cache performance because it makes fewer memory accesses per element on average. Research shows it performs ~10% fewer comparisons than single-pivot quicksort in practice.

☕ Why Java Uses It

Since Java 7, Arrays.sort(int[]) uses dual-pivot quicksort for primitive types. Combined with insertion sort for small subarrays and introspection to avoid worst cases, it provides excellent real-world performance.

🎮 Interactive Visualization

Notice how two pivot values (P1 and P2) create three distinct regions, resulting in three recursive calls instead of two.

---

Summary

Each quicksort variant addresses specific challenges:

Variant	Best For	Trade-off
Lomuto	Learning & teaching	Poor with duplicates
Hoare	General purpose	Fewer swaps, classic efficiency
Three-Way	Duplicate-heavy data	O(n) when all equal!
Median-of-Three	Sorted/reverse input	Balanced partitions
Dual-Pivot	Modern applications	Cache-friendly, used by JDK

🔧 Production Implementations

In practice, production-grade sorting implementations combine multiple techniques:

• Java’s Arrays.sort() — Dual-pivot + insertion sort + introspection
• C++‘s std::sort() — Median-of-three + insertion sort + heapsort fallback
• Python’s sorted() — Timsort (merge sort + insertion sort hybrid)

💡 Key Takeaway: Understanding these variants gives you the tools to choose the right approach for your specific use case and data characteristics.