jsschools

Quick Sort

Divide-and-conquer sort that partitions the array around a pivot, recursively sorting each partition in-place.

Spec ↗

Syntax

quickSort(arr, lo, hi)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes The mutable array to sort in-place.
lo number No Starting index (inclusive). Defaults to 0.
hi number No Ending index (inclusive). Defaults to arr.length - 1.

Returns

void — Sorts the subarray arr[lo..hi] in-place.

Examples

function partition(arr, lo, hi) {
  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;
}

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
}

const nums = [10, 7, 8, 9, 1, 5];
quickSort(nums);
console.log(nums);
Output 
[ 1, 5, 7, 8, 9, 10 ]

// Randomised pivot to avoid O(n²) on sorted input
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const randIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[randIdx], arr[hi]] = [arr[hi], arr[randIdx]];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= arr[hi]) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  const p = i + 1;
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
}

const nums = [1, 2, 3, 4, 5]; // already sorted — safe with random pivot
quickSort(nums);
console.log(nums);
Output 
[ 1, 2, 3, 4, 5 ]

Notes

| Case | Time | Space | |---------|------------|------------| | Best | O(n log n) | O(log n) | | Average | O(n log n) | O(log n) | | Worst | O(n²) | O(n) | Worst case O(n²) occurs when the pivot is always the minimum or maximum (e.g. sorted input with a fixed last-element pivot). Randomised pivot selection or median-of-three makes this astronomically unlikely. Quick sort is **not stable** in its standard form. It has excellent cache performance due to in-place operation and is usually faster in practice than merge sort for in-memory data despite the same average complexity. Three-way partitioning (Dutch Flag) handles duplicate keys efficiently.

See also