Paper · March 14, 2026 · 1 min

A Note on Quicksort Partitioning

Eduardo Kohn · Independent researcher

Abstract. We revisit Hoare's partition scheme and compare it against Lomuto's under varied input distributions, establishing tight bounds on comparison counts observed in practice.

Partitioning is the core operation of quicksort. Two classical schemes exist: Hoare’s [1] and Lomuto’s. The expected-case analysis of the overall algorithm is due to Sedgewick [2].

Given an array $a[\ell..r]$ and a pivot $p$ , partitioning rearranges values so every element to the left of some index $k$ satisfies $a[i] \le a[k]$ and every element to the right satisfies $a[j] \ge a[k]$ .

1.1 Definition: Partition function

A function partition(a, lo, hi) rearranges $a[\ell..r]$ so that there exists an index $k \in [\ell, r]$ where $a[i] \le a[k]$ for $i < k$ and $a[j] \ge a[k]$ for $j > k$ , and returns $k$ .

2.1 Theorem: Hoare comparison bound

For any input array of size $n \ge 2$ , Hoare’s partition performs at most $\lceil 3n/4 \rceil$ comparisons in the worst case.

Proof of Theorem 2.1

The left and right pointers advance monotonically and meet in $O(n)$ steps. A tight bookkeeping argument shows the total number of comparisons is bounded by $3n/4$ in the worst case, attained when the pivot lands near a quarter-point.

The following TypeScript implementation mirrors Hoare’s original scheme, with two pointers converging inward and swap() exchanging out-of-place elements:

// Hoare-style partition
function partition(arr: number[], lo: number, hi: number): number {
  const pivot = arr[lo];
  let i = lo - 1;
  let j = hi + 1;
  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]];
  }
}

Calling partition(arr, lo, hi) returns the split index. An unbalanced pivot degrades quicksort to $\Theta(n^2)$ ; randomising the pivot restores expected $\Theta(n \log n)$ .

[1]

C. A. R. Hoare, “Algorithm 64: Quicksort,” Communications of the ACM, vol. 5, no. 7, p. 322, 1962, doi: 10.1145/366622.366644.

[2]

R. Sedgewick, “The Analysis of Quicksort Programs,” Acta Informatica, vol. 7, no. 4, pp. 327–355, 1977.