Quick Sort

Picks a pivot, partitions array around it, recursively sorts each side.

Best: O(n log n) · Avg: O(n log n) · Worst: O(n²) · Space: O(log n)

66
17
90
27
30
76
68
64
73
35
75
58
72
61
13
Speed5
Size15
TypeScript
function quickSort(arr: number[], lo = 0, hi = arr.length - 1): number[] {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}
function partition(arr: number[], lo: number, hi: number): number {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}