Quick Sort: Divide and Conquer

The Day I Got Stuck on Quick Sort

When I was preparing for coding interviews, I studied sorting algorithms one by one. Bubble sort, selection sort, insertion sort—they were slow but straightforward. Then I hit Quick Sort.

It confused me. "Why is it called Quick if the worst case is O(N²)?", "Why do real-world libraries use it so much?", "How do you pick a good Pivot?" These questions kept piling up.

The textbooks showed short recursive code, but I couldn't grasp how it actually worked, why it used less memory than Merge Sort, what the difference was between Lomuto and Hoare schemes, or what 3-way partition even meant. I just kept rereading "partition around Pivot: smaller to left, larger to right" without really understanding.

The Aha Moment: It's All About the Pivot

I decided to manually partition arrays on paper.

[7, 3, 9, 1, 5]

If I pick 5 as the Pivot:

• Smaller than 5: [3, 1]
• 5
• Larger than 5: [7, 9]

Then for [3, 1], pick 1 as Pivot → [1, 3]. For [7, 9], pick 7 → [7, 9]. Combine: [1, 3, 5, 7, 9].

The core insight: It's all about how you pick the Pivot and partition the array. If you pick poorly—say, always picking the last element in an already sorted array [1, 2, 3, 4, 5]—one side becomes empty and the other has N-1 elements. The recursion tree becomes a straight line, and you get O(N²).

This is the heart of recursion tree analysis. Balanced partitioning gives you a tree depth of log N, with O(N) work per level, totaling O(N log N). Imbalanced partitioning gives you depth N, totaling O(N²).

Two Faces of Partition: Lomuto vs Hoare

The core of Quick Sort is the partition operation. There are two main schemes.

Lomuto Partition Scheme

Lomuto is easier to understand. Pick the last element as Pivot, scan from left, and move smaller elements to the front.

function lomutoPartition(arr, low, high) {
  const pivot = arr[high]; // Last element as Pivot
  let i = low - 1; // Boundary of smaller elements

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // swap
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Place Pivot
  return i + 1; // Pivot's final position
}

Pros: Intuitive. Cons: More swaps, inefficient on already-sorted arrays.

Hoare Partition Scheme

Hoare's scheme is the original by Tony Hoare (creator of Quick Sort). Pointers close in from both ends, swapping elements larger than Pivot on the left with smaller ones on the right.

function hoarePartition(arr, low, high) {
  const pivot = arr[low]; // First element as Pivot
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j; // Pointers crossed

    [arr[i], arr[j]] = [arr[j], arr[i]]; // swap
  }
}

Pros: Fewer swaps, faster on average. Cons: Slightly harder to implement, Pivot's final position isn't as clear.

In practice, Lomuto is popular for simplicity, but performance-critical libraries (like C++ std::sort) use Hoare or variants.

Pivot Selection Strategies: Luck or Strategy?

How you pick the Pivot dramatically affects Quick Sort's performance.

1. First/Last Element

Simplest approach. If the array is already sorted or reverse-sorted, worst case O(N²) happens.

2. Random Pivot

Pick a random element as Pivot. Probabilistically avoids worst case. Widely used in practice.

function randomPivot(arr, low, high) {
  const randomIndex = low + Math.floor(Math.random() * (high - low + 1));
  [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
  return lomutoPartition(arr, low, high);
}

3. Median-of-Three

Pick the median of the first, middle, and last elements as Pivot. Prevents extreme values from becoming Pivot.

function medianOfThree(arr, low, high) {
  const mid = Math.floor((low + high) / 2);
  if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[low] > arr[high]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
  [arr[mid], arr[high]] = [arr[high], arr[mid]]; // Move median to end
  return lomutoPartition(arr, low, high);
}

When There Are Many Duplicates: 3-Way Partition

In arrays with many duplicates (e.g., [5, 3, 5, 5, 1, 5, 9]), 2-way partition is inefficient. Equal elements keep getting recursively processed.

3-Way Partition divides the array into three sections:

• Smaller than Pivot
• Equal to Pivot
• Larger than Pivot

function quickSort3Way(arr, low, high) {
  if (low >= high) return;

  let lt = low; // End of smaller section
  let gt = high; // Start of larger section
  let i = low;
  const pivot = arr[low];

  while (i <= gt) {
    if (arr[i] < pivot) {
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
      gt--;
    } else {
      i++; // Equal to Pivot, just move on
    }
  }

  quickSort3Way(arr, low, lt - 1); // Recurse on smaller section
  quickSort3Way(arr, gt + 1, high); // Recurse on larger section
  // Equal section (lt ~ gt) is already sorted
}

For data with many duplicates, 3-Way Partition gives significant performance improvement.

In-Place Sorting and Cache Locality Power

Quick Sort is preferred over Merge Sort in practice for two reasons.

1. In-Place Sorting

Merge Sort needs a temporary array when merging partitions. Quick Sort only needs swaps within the array, requiring just O(log N) extra space for recursion stack.

2. Cache Locality

Quick Sort processes adjacent regions of the array intensively. During partitioning, it reads and writes contiguous memory, leading to high CPU cache hit rates. Merge Sort copies to temporary arrays, causing more cache misses.

Modern CPUs heavily rely on cache performance, so even with the same theoretical time complexity, Quick Sort is often much faster in practice.

Real-World Libraries Use Hybrids: Introsort

C++ std::sort doesn't use pure Quick Sort. It uses Introsort, a hybrid algorithm.

Introsort Strategy:

1. Start with Quick Sort (fast and cache-friendly)
2. If recursion depth exceeds 2 * log N → switch to Heap Sort (avoid worst case)
3. When partition size drops below 16 → use Insertion Sort (faster for small arrays)

This guarantees O(N log N) worst case while maintaining Quick Sort's average speed.

JavaScript's V8 engine uses TimSort (Insertion Sort + Merge Sort hybrid), but also uses Insertion Sort for small arrays and sometimes Quick Sort-based algorithms for larger ones.

Tail-Call Optimization: Reducing Recursion Stack

Quick Sort makes two recursive calls (left partition, right partition). We can optimize to keep stack depth at O(log N).

Method: Process the larger partition iteratively and recurse only on the smaller one.

function quickSortOptimized(arr, low, high) {
  while (low < high) {
    const pi = partition(arr, low, high);

    // Recurse on smaller partition
    if (pi - low < high - pi) {
      quickSortOptimized(arr, low, pi - 1);
      low = pi + 1; // Iterate on larger partition
    } else {
      quickSortOptimized(arr, pi + 1, high);
      high = pi - 1; // Iterate on larger partition
    }
  }
}

This limits recursion stack depth to O(log N), reducing stack overflow risk for large arrays.

Full Implementation with Step-by-Step Trace

Here's a complete Quick Sort using Lomuto Partition + Median-of-Three Pivot.

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

function medianOfThree(arr, low, high) {
  const mid = Math.floor((low + high) / 2);
  if (arr[low] > arr[mid]) swap(arr, low, mid);
  if (arr[low] > arr[high]) swap(arr, low, high);
  if (arr[mid] > arr[high]) swap(arr, mid, high);
  swap(arr, mid, high); // Move median to end
}

function partition(arr, low, high) {
  medianOfThree(arr, low, high);
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return i + 1;
}

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

// Test
const arr = [7, 2, 9, 1, 5, 3];
console.log('Before:', arr);
quickSort(arr);
console.log('After:', arr); // [1, 2, 3, 5, 7, 9]

Step-by-Step Trace

Initial array: [7, 2, 9, 1, 5, 3]

Step 1: Median-of-Three (low=0, mid=2, high=5)

• arr[0]=7, arr[2]=9, arr[5]=3 → median is 7
• Pivot = 7 (moved to end)

Step 2: Partition around 7

• Smaller than 7: [2, 1, 5, 3]
• 7
• Larger than 7: [9]
• Result: [2, 1, 5, 3, 7, 9] (pi=4)

Step 3: Left recursion [2, 1, 5, 3]

• Pivot = 2
• Partition: [1, 2, 5, 3] (pi=1)
• Left: [1] (done)
• Right: [5, 3]

Step 4: [5, 3] recursion

• Pivot = 3
• Partition: [3, 5]
• Done

Step 5: Right recursion [9]

• Single element, done

Final result: [1, 2, 3, 5, 7, 9]

Closing Thoughts: Why "Quick" Sort?

Studying Quick Sort taught me that algorithms aren't just theory. Memorizing "average O(N log N), worst O(N²)" doesn't explain why Quick Sort is the real-world standard.

I had to implement it myself, manually trace partition steps, experiment with different Pivot strategies. Only then did concepts like Cache Locality, In-Place Sorting, and Tail-Call Optimization become real—not just buzzwords, but actual performance factors.

I also found it fascinating that real-world libraries like Introsort don't use pure Quick Sort. They mix algorithms based on context: switch to Heap Sort to avoid worst case, use Insertion Sort for small arrays. Algorithms compromise with reality.

Quick Sort lives up to its name—it's the fastest sort on average. But that "speed" isn't just about time complexity. It's the combination of memory efficiency, cache utilization, Pivot strategy, and hybrid optimization.

Now whenever I use Array.sort(), I picture Quick Sort picking Pivots and partitioning arrays behind the scenes. And I understand a bit better why it's fast, and how it's optimized.