Day 11: Quick Sort

DAY 11 / 30 · WEEK 2

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

Running example: arr = [5, 2, 8, 1, 9, 3]

Press Play or Step to begin.

Step 0 / 18

▶ Play⏭ Step↺ Reset🔀 Shuffle

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)

j	arr[j]	≤ pivot?	Action	Array after
0	5	No	—	[5, 2, 8, 1, 3]
1	2	Yes	i=0, swap(0,1)	[2, 5, 8, 1, 3]
2	8	No	—	[2, 5, 8, 1, 3]
3	1	Yes	i=1, swap(1,3)	[2, 1, 8, 5, 3]
—	—	—	final swap(2, 4)	[2, 1, 3, 5, 8]

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

Case	Time	Space	Why
Average	O(n log n)	O(log n)	Pivots tend to roughly halve the array — log n levels of recursion, O(n) work per level.
Worst	O(n²)	O(n)	A consistently bad pivot (e.g. always the smallest/largest) splits n elements into 1 and n−1 — n levels deep instead of log n.

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

1. Partition Array According to Given Pivot (LeetCode) — Easy

   Given an array nums and a value pivot, rearrange the elements so everything less than pivot comes first, then everything equal to it, then everything greater — but unlike today’s in-place partition, you must preserve each group’s original relative order.

   Hint

   Today’s swap-based partition doesn’t preserve order, so it won’t work here directly. Instead, walk the array once and push each value into one of three separate arrays (less / equal / greater), then concatenate them — same three-way split, different mechanism.

   Solution

   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];
   }

2. Kth Largest Element in an Array (LeetCode) — Medium

   Find the kth largest element in an unsorted array. (You solved this with a selection-sort approach on Day 8b — today, solve it faster.)

   Hint

   You don’t need to fully sort the array — partition, check which side the kth-largest position falls in, then only recurse into that one side. This is “quickselect,” a close cousin of today’s algorithm.

   Solution

   // 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;
   }

3. 3Sum (LeetCode) — Medium

   Given an array of integers, find all unique triplets that sum to zero. (Combines Day 4’s two-pointer technique with sorting — a classic pairing of today’s and an earlier day’s ideas.)

   Hint

   Sort the array first (any O(n log n) sort, including today’s). Then fix each element in turn as the first of the triplet, and run Day 4’s two-pointer scan on the rest of the array to find pairs that complete the sum to zero. Skip duplicate values as you go to avoid duplicate triplets.

   Solution

   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

1. What causes quicksort’s O(n²) worst case?

• Consistently picking a bad pivot (always smallest/largest)
• It always runs in O(n²) — that’s its normal complexity
• The array being too large to fit in memory

✓ Consistently picking the smallest or largest remaining element as pivot splits n elements into 1 and n-1 every time — n levels of recursion instead of log n.

2. After one call to partition(), what’s guaranteed about the pivot’s position?

• It’s in its final, correct sorted position
• It’s exactly in the middle of the array
• Nothing — it might move again later

✓ After partition, the pivot sits in its exact final sorted position — nothing will ever move it again.

3. What’s quicksort’s main practical advantage over merge sort?

• It sorts in place — much less extra memory than merge sort’s O(n)
• It’s stable and merge sort isn’t
• It guarantees O(n log n) in every case

✓ Quicksort partitions the array in place, needing only O(log n) space for recursion — merge sort needs O(n) auxiliary arrays to merge into.

4. Is the standard (Lomuto partition) quicksort stable?

• No
• Yes

✓ The partition step can swap elements across large distances in the array, which can change the relative order of equal elements.

5. What’s the standard defense against quicksort’s worst case?

• Pick a random (or median-of-three) pivot instead of always the same position
• Sort the array first
• Nothing — the worst case is unavoidable

✓ A random (or median-of-three) pivot makes the O(n²) worst case astronomically unlikely on any given input, rather than depending on the input already being adversarial.