Quick Sort

Quick Sort

Quick sort is the rockstar of sorting algorithms — fast, efficient, and used everywhere. Like merge sort, it uses divide and conquer, but it works from the top down. You pick a pivot element, partition the array so smaller elements go left and larger go right, then recursively sort the partitions.

The genius of quick sort is that the partitioning happens in place — no extra array needed. That O(log n) space for the recursion stack is much better than merge sort's O(n) for temporary arrays. This is why quick sort often wins in practice despite having a worse worst case.

Pivot Selection and Partitioning

Pivot selection is critical. Pick the median element and you get perfect balance. Pick the smallest or largest and you get terrible performance. Common strategies: pick the first element, last element, middle element, or use random selection. Random pivots give quick sort its expected O(n log n) performance.

Partitioning is straightforward: scan through the array, moving elements smaller than the pivot to the left and larger to the right. Then place the pivot in its correct position. This single pass through the data is O(n), and after it, the pivot is in its final sorted position.

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}
function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}
console.log(quickSort([10, 7, 8, 9, 1, 5]));

Average vs Worst Case

Average case: O(n log n). With good pivot selection, the partitions are roughly equal, giving you the same logarithmic depth as merge sort. Worst case: O(n²). This happens when you consistently pick the worst pivot — like choosing the largest element as pivot for an already-sorted array.

In practice, the worst case almost never occurs, especially with randomized pivot selection. The expected runtime is always O(n log n), and the constant factors are smaller than merge sort's. That's why most standard library sort implementations use quick sort or a hybrid.

In-Place Sorting Advantage

Quick sort's biggest practical advantage is in-place sorting. You don't need to allocate and copy to temporary arrays like merge sort. The space complexity is just O(log n) for the recursion stack. For large datasets, this means less memory pressure and better cache performance.

The trade-off is that quick sort is not stable — equal elements might get shuffled during partitioning. If stability matters, use merge sort. Otherwise, quick sort's speed and low memory usage make it the default choice for most sorting tasks.