Quick Sort

Picks a pivot, partitions elements around it, then recursively sorts each partition.

0 elements

SpdSize50

>Ready — Quick Sort

Code

function quickSort(lo, hi) {
  if (lo >= hi) return;
  // Partition with last element as pivot
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (compare(hi, j)) {
      swap(i, j);
      i++;
    }
  }
  swap(i, hi);
  quickSort(lo, i - 1);
  quickSort(i + 1, hi);
}
quickSort(0, length - 1);

function quickSort(lo, hi) {
  if (lo >= hi) return;
  // Partition with last element as pivot
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (compare(hi, j)) {
      swap(i, j);
      i++;
    }
  }
  swap(i, hi);
  quickSort(lo, i - 1);
  quickSort(i + 1, hi);
}
quickSort(0, length - 1);

Analysis

BEST O(n log n)

AVG O(n log n)

WORST O(n²)

SPACE O(log n)

UNSTABLE

Quick Sort picks a pivot and partitions the array so smaller elements go left, larger go right. It recursively sorts both sides. Pivot choice matters — bad pivots cause O(n²), but average case is among the fastest.

Edit in playground→