Quick sort: partition around a pivot

Quick sort picks one value as the pivot and rearranges the array so that everything smaller than the pivot comes before it and everything else after it — a step called partitioning. The pivot is now in its final place, and the two sides are sorted the same way, recursively.

Partitioning 10, 80, 30, 90, 40, 50, 70 around the pivot 70. Afterwards the values smaller than 70, which are 10, 30, 40 and 50, are on its left; 70 sits at index 4, its final place; and the larger values, 90 and 80, are on its right, not yet in order. Each side is then sorted the same way.

How it works

If the range has 0 or 1 values, it's sorted.
Partition: take the last value as the pivot. Walk through the range with j, keeping a boundary i — everything before i is smaller than the pivot. When nums[j] is smaller, swap it to i and move i on. Finally swap the pivot into i.
The pivot is now in its final place. Quick-sort the part before it and the part after it.

Dry-run simulator

Quick sort (Lomuto partition)

Each partition puts one pivot in its final place; then each side is partitioned the same way.

The code

1function quickSort(nums, lo = 0, hi = nums.length - 1) {2  if (lo >= hi) return nums;                      // 0 or 1 values: nothing to do3  const p = partition(nums, lo, hi);4  quickSort(nums, lo, p - 1);                     // sort the smaller values...5  quickSort(nums, p + 1, hi);                     // ...and the bigger ones6  return nums;7}8 9function partition(nums, lo, hi) {10  const pivot = nums[hi];                         // Lomuto: the last value is the pivot11  let i = lo;                                     // nums[lo..i) are smaller than the pivot12  for (let j = lo; j < hi; j++) {13    if (nums[j] < pivot) {14      [nums[i], nums[j]] = [nums[j], nums[i]];15      i++;16    }17  }18  [nums[i], nums[hi]] = [nums[hi], nums[i]];      // the pivot lands in its final place19  return i;20}

JavaScript20 lines

How fast is it?

Each level of partitioning looks at every value once. If pivots land near the middle, the ranges halve and there are about log n levels: O(n log n), which is the average for random input. If the pivot is always the smallest or largest value — for example taking the last value of an already sorted array — one side is empty every time, there are n levels, and it degrades to O(n²). The recursion uses O(log n) stack on average, O(n) in that worst case.

Best and average: O(n log n) time, O(log n) space. Worst: bad pivots: O(n²) time, O(n) space.

The usual fix is a random pivot: swap a random value of the range into nums[hi] before partitioning. Then no particular input is reliably bad, and O(n²) becomes vanishingly unlikely. Production versions also pick the median of three values and switch to insertion sort for tiny ranges.

Properties

Not stable — partition swaps can jump a value over an equal one.
In-place — only the recursion stack is extra.
Very fast in practice — tight loops over contiguous memory make it the fastest comparison sort on random arrays.

When to use it

It's the general-purpose in-memory sort: C++'s std::sort is introsort (quick sort that switches to heap sort if the recursion goes too deep), and Java sorts primitives with dual-pivot quick sort. Its partition step is a pattern on its own — Sort Colors, Sort Array By Parity and Kth Largest Element (quickselect) are all partitions.

Key takeaways

Partition around a pivot so it lands in its final place, then sort both sides.
O(n log n) on average, O(n²) with consistently bad pivots — randomise the pivot.
In-place but not stable; usually the fastest sort for arrays in memory.

Prev Next

Was this helpful?