Quick Sort

Pick a pivot, partition around it, recurse — fast in-place sorting.

What it is

Quick sort picks a pivot value, rearranges the array so everything smaller is left of it and everything bigger is right of it (partitioning), then recurses on each side. Average case is O(n log n) and it sorts in-place (unlike merge sort), which usually makes it faster in practice — but a bad pivot choice on already-sorted or adversarial input degrades it to O(n²).

Real-world examples

Sorting a line of people by height by picking one person as a reference, sending everyone shorter to their left and taller to their right, then repeating within each group.
A tournament bracket-style elimination that narrows a group down by repeatedly splitting around a benchmark.

Where you've probably used this already

Quickselect — reusing just the partition step to find the 'kth largest/smallest element' in O(n) average without fully sorting.
In-memory sort implementations in databases and language runtimes when data fits comfortably in RAM.
Explaining in an interview why 'sort then take index k' is worse than an O(n) selection algorithm for a single order-statistic query.

Complexity

Time (average) O(n log n)

Time (worst case) O(n²) — bad pivot choices

Space O(log n) — recursion stack, sorts in-place

Stable? No

Code

// Quick Sort — pick a "pivot", push everything smaller to its left and
// everything bigger to its right, then recurse on each side.
// Average O(n log n), worst case O(n^2) on already-sorted/bad pivots,
// but usually faster in practice than Merge Sort because it sorts
// in-place (less memory shuffling).

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high]; // pick the last element as pivot
  let i = low - 1; // boundary of "smaller than pivot" region

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  // place the pivot right after the "smaller" region
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1; // final index of the pivot
}

// --- Example Usage ---
console.log("quickSort([5,2,9,1,7,3]):", quickSort([5, 2, 9, 1, 7, 3]));
// [1,2,3,5,7,9]

// Where this shows up:
// - "kth largest element" problems use the partition step alone
//   (quickselect) to find an answer in O(n) average without full sorting
// - database query planners choosing pivot-based partitioning for
//   in-memory sorts when data fits in RAM