Quicksort

Quicksort is one of the most widely used sorting algorithms. It works by selecting a pivot element and partitioning the array around it.

How It Works

1. Pick a pivot element from the array.
2. Partition — rearrange so elements less than the pivot come before it, and elements greater come after.
3. Recurse on the two sub-arrays.

Example

function quicksort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);

  return [...quicksort(left), ...middle, ...quicksort(right)];
}

console.log(quicksort([3, 6, 8, 10, 1, 2, 1]));
// [1, 1, 2, 3, 6, 8, 10]

Complexity

Why O(n²) in the Worst Case?

The worst case happens when the pivot is always the smallest or largest element — the partition is maximally unbalanced. Choosing a random pivot or median-of-three avoids this in practice.

Compared to Merge Sort

• Quicksort is in-place (lower memory overhead).
• Merge sort is stable (preserves order of equal elements).
• Quicksort tends to be faster in practice due to better cache locality.