DAY 11 / 30 · WEEK 2

Quick Sort

Goal of the day

• Implement quicksort: pick a pivot, partition around it, recurse on both sides.
• Understand why the average case is O(n log n) but the worst case is O(n²).
• Watch the pivot land in its exact final sorted position on every partition step.

Concept

Line up a group of people to sort by height. Pick one person as a reference point — the pivot — and have everyone shorter step to their left, everyone taller step to their right. Once that's done, the pivot is standing in exactly the spot they'll occupy in the final sorted line — nobody will ever move them again. Now repeat the same process independently on the "shorter" group and the "taller" group, each shrinking the problem until every group has 0 or 1 people left.

This is different from Day 10's merge sort: merge sort does easy splits (always exactly in half) but hard combines (a real merge step). Quicksort does hard splits (the partition does real work) but trivial combines (there's nothing left to do — once both sides are sorted, the whole array is sorted, because the pivot was already in place).

Diagram

Interactive visualization: full sort, partition + recurse

The code

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);   // everything left of the pivot
    quickSort(arr, p + 1, hi);   // everything right of the pivot
  }
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];   // pick the last element as pivot
  let i = lo - 1;          // boundary of "elements ≤ pivot seen so far"
  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]]; // pivot into its final slot
  return i + 1; // the pivot's final index
}

Line by line:

• partition — i tracks the boundary of the "small" region. Every time arr[j] <= pivot, we grow that region by one and swap the new small element into it. Everything between i+1 and j at any moment is "seen, but bigger than pivot."
• The final swap places the pivot right after the last "small" element — that's its permanent, correct position. This is why quicksort needs no separate merge step, unlike Day 10.
• quickSort's if (lo < hi) is the base case: a range of 0 or 1 elements needs no work.

Dry run: partition([5, 2, 8, 1, 3], lo=0, hi=4, pivot=3)

3 lands at index 2 — everything before it (2, 1) is ≤ 3, everything after (5, 8) is not yet sorted but is guaranteed > 3.

Complexity

Space is the recursion depth, not extra arrays — quicksort partitions in place, unlike merge sort's O(n) auxiliary arrays. That's quicksort's main practical advantage.

Interview corner

• What causes quicksort's O(n²) worst case? Consistently picking a bad pivot — the smallest or largest remaining element every time. On an already-sorted array, always picking the last element as pivot (like today's code) triggers exactly this.
  ↳ Common follow-up: "How do you avoid this?" — pick a random pivot, or the median of the first/middle/last elements, instead of always the same position. This makes the worst case astronomically unlikely, not impossible.
• Quicksort vs. merge sort — when would you choose each? Quicksort is usually faster in practice (better cache locality, in-place, smaller constant factor), but merge sort has a guaranteed O(n log n) and is stable. If worst-case guarantees matter (e.g. real-time systems) or ties must preserve order, merge sort wins.
  ⚠ Trap: don't say "quicksort is always faster" — it's faster on average, with a worse worst case. Precision here signals real understanding.
• Is quicksort stable? No — the partition step swaps elements across potentially large distances, which can reorder equal elements relative to each other.

How to talk through it out loud: name the trade-off explicitly — "quicksort partitions in place, so it avoids merge sort's O(n) extra space, but that trade-off is a worst case that depends on pivot choice." Following up with how you'd choose a pivot to avoid the worst case (random or median-of-three) shows you know the failure mode and how to defend against it, not just the happy path.

Practice problems

function pivotArray(nums, pivot) {
  const less = [], equal = [], greater = [];
  for (const n of nums) {
    if (n < pivot) less.push(n);
    else if (n === pivot) equal.push(n);
    else greater.push(n);
  }
  return [...less, ...equal, ...greater];
}

// Quickselect: like quicksort, but only recurse into the side that
// contains the answer — average O(n) instead of O(n log n).
function findKthLargest(nums, k) {
  const target = nums.length - k; // index of kth largest in sorted order
  let lo = 0, hi = nums.length - 1;
  while (true) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p];
    else if (p < target) lo = p + 1;
    else hi = p - 1;
  }
}
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 threeSum(nums) {
  nums = [...nums].sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate first elements
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++; right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return result;
}

Quiz