How does quicksort (Hoare partition) work?

AlgorithmsJunior~3 min read

Short answer

Quicksort (Hoare partition) is a "divide and conquer" algorithm: choose a pivot element, rearrange the elements so that everything ≤ pivot is on the left and everything ≥ pivot is on the right (Hoare partition), then recursively sort both parts.
Complexity: on average O(n log n), worst case O(n²) (with a poorly chosen pivot), memory O(log n) due to recursion depth. The algorithm is in-place and unstable.

Quicksort is a classic in-place sorting algorithm. The key idea: choose a pivot and "split" the array into two parts so that all elements on the left do not exceed the pivot, and elements on the right are not less than the pivot. Then independently sort the left and right parts. The Hoare scheme is a specific way of performing this partition using two pointers moving inward from the ends of the array.

Hoare scheme: steps

Choose a pivot element (for example, the middle one by index, or using the median-of-three rule).
Set two pointers: i = low - 1 and j = high + 1.
Move i to the right while A[i] < pivot. Move j to the left while A[j] > pivot.
If i ≥ j, return j as the partition index (the last index of the left part).
Otherwise, swap A[i] and A[j] and continue.
After partitioning, recursively call the sort for [low..j] and [j+1..high].

Pseudocode (Hoare partition)

partition_hoare(A, low, high):
  pivot := A[(low + high) // 2]
  i := low - 1
  j := high + 1
  while true:
    repeat i := i + 1 until A[i] >= pivot
    repeat j := j - 1 until A[j] <= pivot
    if i >= j:
      return j  // the index that splits the array into [low..j] and [j+1..high]
    swap A[i], A[j]

quicksort(A, low, high):
  if low >= high: return
  p := partition_hoare(A, low, high)
  quicksort(A, low, p)
  quicksort(A, p + 1, high)

Implementation in JavaScript (Hoare scheme)

function partitionHoare(a, low, high) {
  const pivot = a[Math.floor((low + high) / 2)];
  let i = low - 1;
  let j = high + 1;
  while (true) {
    do { i++; } while (a[i] < pivot);
    do { j--; } while (a[j] > pivot);
    if (i >= j) return j; // j - boundary of the left part
    [a[i], a[j]] = [a[j], a[i]];
  }
}

function quicksort(a, low = 0, high = a.length - 1) {
  if (low >= high) return a;
  const p = partitionHoare(a, low, high);
  quicksort(a, low, p);
  quicksort(a, p + 1, high);
  return a;
}

// Example:
const arr = [9, 3, 7, 1, 8, 2, 5];
console.log(quicksort(arr)); // [1, 2, 3, 5, 7, 8, 9]

Important: recursion boundaries in the Hoare scheme

partitionHoare returns an index p such that the left part is [low..p] and the right part is [p+1..high]. The mistake "quicksort(a, low, p - 1)" leads to skipped elements and/or an infinite loop.

Partitioning example (briefly)

For the array [9, 3, 7, 1, 8, 2, 5], pivot = the middle element by index (7). i moves right until 9 (stops, 9 ≥ 7), j moves left until 5 (stops, 5 ≤ 7). We swap 9 ↔ 5 → [5, 3, 7, 1, 8, 2, 9]. Next, i stops at 7, j at 2 - we swap → [5, 3, 2, 1, 8, 7, 9]. Then i crosses j - p points to the end of the left part. After that, the recursive calls sort the subarrays.

Choosing the pivot

First/last element: simple, but poor on already sorted arrays (worst case).
Random pivot: reduces the chance of the worst case to a rare occurrence.
Median-of-three (median of the first/middle/last element): a simple heuristic against degradation on partially sorted data.

Complexity

Average: O(n log n) - with balanced partitions.
Worst: O(n²) - with strong imbalance (for example, an already sorted array and a bad pivot).
Memory: O(log n) - average recursion depth (worst case - O(n)).

Stability and properties

In-place: requires no extra memory for the array (except the call stack).
Unstable: the relative order of equal elements is not preserved.
Sensitive to pivot choice; for a large number of duplicates, 3-way partitioning is better.

Duplicates and 3-way partitioning (speeds things up with many equal elements)

Instead of the classic 2-way partition, you can split the array into three zones: < pivot, = pivot, > pivot. This reduces the recursion depth when there are many duplicates.

function quicksort3way(a, low = 0, high = a.length - 1) {
  if (low >= high) return a;
  const pivot = a[Math.floor((low + high) / 2)];
  let lt = low, i = low, gt = high;
  while (i <= gt) {
    if (a[i] < pivot) {
      [a[lt], a[i]] = [a[i], a[lt]];
      lt++; i++;
    } else if (a[i] > pivot) {
      [a[i], a[gt]] = [a[gt], a[i]];
      gt--;
    } else {
      i++;
    }
  }
  quicksort3way(a, low, lt - 1);
  quicksort3way(a, gt + 1, high);
  return a;
}

Iterative version (without recursion)

function quicksortIterative(a) {
  const stack = [[0, a.length - 1]];
  while (stack.length) {
    const [low, high] = stack.pop();
    if (low >= high) continue;
    const p = partitionHoare(a, low, high);
    // Process the smaller subarray first (a heuristic to reduce stack depth)
    if (p - low < high - (p + 1)) {
      stack.push([p + 1, high]);
      stack.push([low, p]);
    } else {
      stack.push([low, p]);
      stack.push([p + 1, high]);
    }
  }
  return a;
}

Typical interview mistakes

Incorrect recursion boundaries for the Hoare scheme: you need to sort [low..p] and [p+1..high].
Confusion between Hoare and Lomuto partitioning (with Lomuto, the pivot is usually placed at the end and the pivot's position is returned; with Hoare, the pivot does not necessarily end up in its "own" place after partitioning).
Choosing a bad pivot (for example, the first element) on nearly sorted data → degradation to O(n²).
Off-by-one errors with the i/j indices, incorrect stop conditions and comparisons.

When to use

General-purpose sorting of numbers/comparable objects in memory, when stability is not critical.
With a large number of duplicates: consider 3-way partitioning or a hybrid (introsort).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.