How does quicksort work?

Quicksort's performance depends almost entirely on pivot choice. A balanced split gives log n levels; a consistently bad split gives n levels. Randomised pivots or median-of-three reduce the chance of hitting the worst case on real input.

function quicksort(values, low = 0, high = values.length - 1) {
  if (low >= high) return values;
  const pivotIndex = partition(values, low, high);
  quicksort(values, low, pivotIndex - 1);
  quicksort(values, pivotIndex + 1, high);
  return values;
}

function partition(values, low, high) {
  const pivot = values[high];
  let smaller = low;
  for (let i = low; i < high; i++) {
    if (values[i] < pivot) {
      [values[i], values[smaller]] = [values[smaller], values[i]];
      smaller += 1;
    }
  }
  [values[smaller], values[high]] = [values[high], values[smaller]];
  return smaller;
}

Why the worst case happens

• Choosing the last element as pivot on already sorted input gives O(n^2)
• Each partition removes only one element in the worst case
• Randomised or median pivots make the bad case unlikely
• Recursion depth is O(log n) average and O(n) worst
• Quicksort is not stable

Quicksort is usually faster than merge sort in practice because it sorts in place and has good cache behaviour. Merge sort has the safer worst-case guarantee. In languages with a built-in sort, the implementation is often a hybrid that switches to insertion sort for small ranges.