⚡ Quicksort

How It Works

Quicksort is a divide-and-conquer algorithm. It picks a pivot, partitions the array so elements smaller than the pivot go left and larger go right, then recursively sorts each half.

Lomuto Partition Scheme

1. Pick the last element as pivot
2. Maintain a store index i (left boundary of "greater than pivot" elements)
3. Scan from lo to hi-1 with pointer j
4. If arr[j] ≤ pivot, swap arr[i] and arr[j], increment i
5. Finally place pivot at i — it's now in its sorted position
6. Recurse on [lo, i-1] and [i+1, hi]

Key Code (iterative with explicit stack)

function* quicksortGen(arr) {
  const stack = [[0, arr.length - 1]];  // use stack to avoid true recursion
  while (stack.length > 0) {
    const [lo, hi] = stack.pop();
    if (lo >= hi) continue;

    // partition
    const pivot = arr[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
      yield { type: 'compare', i, j, pivotIdx: hi, lo, hi };
      if (arr[j] <= pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        yield { type: 'swap', i, j };
        i++;
      }
    }
    [arr[i], arr[hi]] = [arr[hi], arr[i]];  // place pivot
    yield { type: 'placed', pivotIdx: i };

    stack.push([lo, i - 1]);
    stack.push([i + 1, hi]);
  }
}

Why It's Fast

On average, each partition splits the array roughly in half, giving O(n log n) total work. With n=40: Quicksort ≈ 40×6 = 240 ops, Bubble sort ≈ 40²/2 = 800 ops — 3× faster.

Complexity