Quick Sort

Quick sort is the workhorse of in-memory sorting. Pick one value as the pivot, then partition the list so everything smaller sits left of it and everything larger sits right. The pivot is now in its final position — and you sort the two sides the same way. It's usually the fastest comparison sort in practice, sorting within the array itself.

The partition step is the whole trick

Partitioning is what does the real work; the recursion just glues it together. In the common Lomuto scheme you pick the last element as pivot and sweep a pointer across, keeping a boundary i for 'everything left of here is smaller than the pivot'. Each value < pivot is swapped to the boundary. At the end you swap the pivot into the boundary slot — and it's home.

1. 1Choose a pivot (here, the last element).
2. 2Walk a pointer j across the range; whenever arr[j] < pivot, swap it to the boundary i and advance i.
3. 3After the sweep, swap the pivot into position i — now everything left is smaller, everything right is larger.
4. 4Recurse on the left part and the right part, excluding the pivot.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // pivot to its final spot
  quickSort(arr, lo, i - 1);
  quickSort(arr, i + 1, hi);
  return arr;
}