THE SAME EIGHT VALUES, EVERY ALGORITHM
DOES IT MERGE?
Everyone can name three sorting algorithms. Far fewer can say which one a problem is quietly asking for — stable or not, in place or not, already-nearly-sorted or adversarial. That choice is the whole topic.
This is not a list of problems. It is 9 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
10 PROBLEMS · EVERY ONE LINKS TO A JUDGE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Nobody is asked to “write a sorting algorithm” in an interview. You are handed constraints and expected to hear which one they permit — and twice in this deck the answer is that sorting is not the answer at all.
No stability or memory constraint stated.
Library sort — or quick sort if asked to implementO(n log n)Ties must not be reordered — usually a second sort key.
Merge sort · insertion sortO(n log n) · O(n) spaceBoth in-place and worst-case bounded.
Heap sort — the only one giving bothO(n log n) · O(1)Ages, scores, 0/1/2, letters of an alphabet.
Counting sort — no comparisons at allO(n + k)Pair-counting at a size that forbids all-pairs.
Merge sort, counting during the mergeO(n log n)Order is not the answer, it is what makes the answer cheap.
Sort by start, then one sweepO(n log n)Before writing anything, read the input bound and it tells you the complexity you are allowed. Type a value for n and the row that survives lights up.
THE GOLD-EDGED ROWS ARE WHERE THIS TOPIC LIVES · QUADRATIC SORTS DIE AT 10³ · COUNTING AND RADIX REACH 10⁷
Nine units. The first five are the sheet; the last four are lectures with no sheet row at all, kept because they are where the comparison lower bound gets broken — the best idea in the topic, and the sheet does not cover it.
You need to sort 10⁵ integers within a one-second limit. Which of these is already too slow?
10⁵ squared is 10¹⁰, and a second buys you roughly 10⁸ operations — so the quadratic sorts are out by two orders of magnitude before you write a line. n log n here is about 1.7 × 10⁶, which is nothing. The constraint told you which family to reach for, and the next slide makes that reading mechanical.
A sort is called stable when…
Stability is about ties. If two records compare equal, a stable sort leaves them in their original order. It sounds academic until you sort employees by department having already sorted them by name — with an unstable sort the names scramble inside each department. Merge and insertion are stable; quick, heap and shell are not, and that is often the deciding factor.
One pass turns [5, 1, 4, 2] into [1, 5, 2, 4]. Compare the two arrays: what kind of move produced this?
Two swaps of adjacent values. Read the pairs: 5 and 1 traded places, then 4 and 2 did. Nothing moved more than one slot, and no value jumped across the array — so whatever did this only ever compares neighbours. That is a real constraint, and it is why this family cannot be fast: to move a value k places you need k separate swaps. Unit 01 names the three algorithms that work this way; the point here is only that you can see the limitation in the data before you know any of their names.
Three algorithms, one shape: a growing sorted region on one side and a shrinking unsorted region on the other. What separates them is where the sorted region is and what one pass costs to extend it — and that difference is the reason two of them survive in real libraries and one does not.
HOW DO YOU SORT WITH NOTHING BUT COMPARISONS AND SWAPS?
Hand selection sort an array that is already perfectly sorted. What does it cost?
Still O(n²), and this is the property the lecture opens with. Selection sort's inner loop has no exit condition that depends on the data — it looks at every remaining element to be certain it has the minimum, sorted input or not. It performs zero swaps on sorted input and the full n(n−1)/2 = 28 comparisons anyway. Comparisons are fixed; only the swap count reacts to the input.
Bubble sort runs ONE complete pass over [7, 2, 9, 4, 1, 8, 3, 6]. What sits at the last index afterwards?
9. Every comparison pushes the larger of the pair one slot right, so the maximum gets picked up wherever it sits and carried all the way to the end — that is the “bubbling” the name refers to. One pass places exactly one value, and it is always the maximum of the unsorted region. Step the visualiser in PREDICT mode and it asks you this once per pass.
This is the insertion sort shift loop, and one line is wrong. It compiles, it runs, and it silently returns a wrong array. Which line?
while (j >= 0 && a[j] > key) { a[j] = a[j + 1]; // shift j--; } a[j + 1] = key;
The assignment is backwards. Shifting means copying the larger value into the gap on its right, so it reads a[j + 1] = a[j]. Written the other way it copies the gap's stale contents leftward, overwriting real data with garbage — no crash, no warning, just a wrong array. This is the exact line the lecture slows down for: the gap moves left, the values move right.
A log file arrives almost sorted — a handful of entries are out of place. Which of the three finishes fastest, and why?
Insertion. Its inner while stops as soon as it meets something smaller than the key, so on nearly-sorted input it barely runs and the whole sort collapses to O(n). Bubble's flag also gives O(n), but only on input that is already fully sorted — a single misplaced element at the front still costs it a full set of passes to carry across. This is exactly why real library sorts hand small or nearly-ordered ranges to insertion sort rather than continuing to recurse.
The pass never stops early and never learns anything from the data: it looks at every remaining value before it moves a single one. Comparisons are fixed at 28 no matter what you feed it — but it makes at most n−1 swaps, which is why it survives where writes are expensive.
Every swap moves a value exactly one slot, so a value at the wrong end has to be carried across the array one exchange at a time. Watch the swap counter climb. The one thing it does better than selection: a clean pass proves the array is sorted, so sorted input costs O(n).
The left side is always sorted. Each new value is lifted out and the larger ones shift right to open a gap — one write per shift, not three per swap. On nearly-sorted input the inner loop barely runs, which is why real libraries switch to insertion sort for small or almost-ordered ranges.
The task names the algorithm outright, so the signal is not which algorithm but which invariant you have to protect: after pass i, the first i slots are final and are never read again.
Split the array into a sorted prefix and an unsorted tail. One pass finds the minimum of the tail and swaps it to the tail's front, which extends the prefix by one. Repeat n−1 times — the last element has nowhere left to go, so it is already correct by elimination.
// Selection sort: find the minimum of the tail, then move it ONCE. // The scan records an index; nothing is written until the scan is over. void selectionSort(vector<int>& a) { int n = a.size(); for (int i = 0; i < n - 1; i++) { // n-1 passes, not n int mn = i; // assume the front is smallest for (int j = i + 1; j < n; j++) // scan the WHOLE tail, always if (a[j] < a[mn]) mn = j; // record only, do not swap here swap(a[i], a[mn]); // ONE write per pass, at most } }
// Selection sort: find the minimum of the tail, then move it ONCE. // The scan records an index; nothing is written until the scan is over. void selectionSort(int[] a) { int n = a.length; for (int i = 0; i < n - 1; i++) { // n-1 passes, not n int mn = i; // assume the front is smallest for (int j = i + 1; j < n; j++) // scan the WHOLE tail, always if (a[j] < a[mn]) mn = j; // record, do not swap int t = a[i]; a[i] = a[mn]; a[mn] = t; // ONE write per pass } }
# Selection sort: find the minimum of the tail, then move it ONCE. # The scan records an index; nothing is written until the scan is over. def selection_sort(a): n = len(a) for i in range(n - 1): # n-1 passes, not n mn = i # assume the front is smallest for j in range(i + 1, n): # scan the WHOLE tail, always if a[j] < a[mn]: mn = j # record only, do not swap here a[i], a[mn] = a[mn], a[i] # ONE write per pass, at most
Swapping inside the scan instead of after it is the mistake that still produces a sorted array — so the judge passes it and you never learn. It turns one swap per pass into up to n−1 of them, and selection sort's only advantage over bubble sort is that it writes at most n−1 times. Find the index first, swap once.
The walkthrough for #01 Selection Sort. Watch it, then go straight back and write it yourself.
Adjacent comparison only. The moment a problem restricts you to swapping neighbours, the number of swaps you need is fixed — it is the inversion count — and bubble sort is what performs exactly that many.
Walk the array comparing each pair of neighbours and swap them if they are out of order. The largest value meets a smaller neighbour at every step, so it gets carried to the end in a single pass. Shrink the range by one and repeat. If a whole pass swaps nothing, no pair is out of order anywhere — the array is sorted and you can stop.
// Bubble sort: swap neighbours only. The flag is the whole optimisation // and it must be reset once per PASS -- outside the loop it never re-arms. void bubbleSort(vector<int>& a) { int n = a.size(); for (int i = n - 1; i > 0; i--) { bool didSwap = false; // INSIDE: reset every pass for (int j = 0; j < i; j++) // j < i: the tail is already final if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); // NEIGHBOURS only didSwap = true; } if (!didSwap) break; // a clean pass proves it is sorted } }
// Bubble sort: swap neighbours only. The flag is the whole optimisation // and it must be reset once per PASS -- outside the loop it never re-arms. void bubbleSort(int[] a) { int n = a.length; for (int i = n - 1; i > 0; i--) { boolean didSwap = false; // INSIDE: reset every pass for (int j = 0; j < i; j++) // j < i: the tail is already final if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; didSwap = true; } if (!didSwap) return; // already sorted: O(n) best case } }
# Bubble sort: swap neighbours only. The flag is the whole optimisation # and it must be reset once per PASS -- outside the loop it never re-arms. def bubble_sort(a): n = len(a) for i in range(n - 1, 0, -1): did_swap = False # INSIDE: reset every pass for j in range(i): # range(i): the tail is final if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] # NEIGHBOURS only did_swap = True if not did_swap: # a clean pass proves it is sorted break
Declaring didSwap outside the outer loop is the version that looks optimised and is not. Set to true by the very first real swap, it never returns to false, so the early exit can never fire and the best case quietly reverts to O(n²). The answer stays correct, which is exactly why nobody notices. It belongs inside the outer loop, reset once per pass.
The walkthrough for #02 Bubble Sort. Watch it, then go straight back and write it yourself.
Elements arriving one at a time, or an array that is already nearly in order. Both point at insertion sort, because it is the only one of the three whose cost drops when the input is already good — and the only one that can sort a stream it has not finished reading.
Treat the left of the array as sorted — one element is sorted by definition. Lift the next value out into a variable, leaving a genuine hole. Slide every larger value one slot right; the hole travels left with them. When you meet something smaller, the hole is exactly where the value belongs, so drop it in.
// Insertion sort: SHIFT the larger values right, then drop the key in. // One write per shift -- a swap would cost three, for the same movement. void insertionSort(vector<int>& a) { int n = a.size(); for (int i = 1; i < n; i++) { // a[0] is a sorted prefix already int key = a[i]; // lift it out, leaving a gap int j = i - 1; while (j >= 0 && a[j] > key) { // '>' not '>=' -- keeps it STABLE a[j + 1] = a[j]; // shift right; the gap moves left j--; } a[j + 1] = key; // drop into the gap } }
// Insertion sort: SHIFT the larger values right, then drop the key in. // One write per shift -- a swap would cost three, for the same movement. void insertionSort(int[] a) { int n = a.length; for (int i = 1; i < n; i++) { // a[0] is a sorted prefix already int key = a[i]; // lift it out, leaving a gap int j = i - 1; while (j >= 0 && a[j] > key) { // '>' not '>=' -- keeps it STABLE a[j + 1] = a[j]; // shift right into the gap j--; } a[j + 1] = key; // drop the key into the hole } }
# Insertion sort: SHIFT the larger values right, then drop the key in. # One write per shift -- a swap would cost three, for the same movement. def insertion_sort(a): n = len(a) for i in range(1, n): # a[0] is a sorted prefix already key = a[i] # lift it out, leaving a gap j = i - 1 while j >= 0 and a[j] > key: # '>' not '>=' -- keeps it STABLE a[j + 1] = a[j] # shift right; the gap moves left j -= 1 a[j + 1] = key # drop into the gap
Writing the inner loop as a chain of swap calls instead of shifts sorts correctly and costs three times the writes — each swap is a read, two writes and a temporary, where a shift is one write. Worse, using a[j] >= key rather than > makes the sort unstable: equal elements get reordered, and every problem that sorts records by one field while relying on a previous ordering silently breaks.
The walkthrough for #03 Insertion Sort. Watch it, then go straight back and write it yourself.
The first algorithm here that is not quadratic — and the reason is structural, not clever. Splitting costs nothing and compares nothing; all the work is in putting two already sorted halves back together, and that is cheap precisely because only the two fronts can ever compete.
HOW DO YOU GET BELOW n² BY DOING NOTHING ON THE WAY DOWN?
In merge sort, where do the comparisons between elements actually happen?
Only in the merge. The split is pure arithmetic — mid = (lo + hi) / 2 — and never looks at a value. This is the point the lecture opens on and it is what makes the cost analysis so clean: each of the log n levels does O(n) merging work and nothing else, so the total is O(n log n) with no cases and no caveats.
The final merge combines the sorted halves [2, 4, 7, 9] and [1, 3, 6, 8]. Which value is written THIRD?
3. Only the two fronts can compete: 2 vs 1 → write 1; then 2 vs 3 → write 2; then 4 vs 3 → write 3. That is the whole reason a merge is linear rather than quadratic — you never look past the front of either half, because both halves are already sorted. Run the visualiser in PREDICT mode and it asks you exactly this at every merge.
This is the copy-back after a merge. It compiles, runs, and scrambles the array on every subarray except the leftmost. Which line is wrong?
for (int i = 0; i < temp.size(); i++) a[i] = temp[i]; // temp holds the merged range a[low..high]
a[low + i] = temp[i]. The temp array is indexed from 0 but the range it belongs to starts at low. Forget the offset and every merge dumps its result at the front of the array. The leftmost subarray has low == 0, so it works there — which is exactly why this bug survives a quick test and then fails the judge. The lecture writes this offset out deliberately.
Merge sort needs O(n) extra space and quick sort needs O(1). Why is merge sort still the one used for linked lists?
Random access. A merge only ever reads the front of each half and advances — perfectly natural for a linked list, and on a list you can relink instead of copying, so the O(n) space disappears too. Partitioning, by contrast, walks two pointers inward from both ends, and walking backwards through a singly linked list is exactly what it cannot do.
Nothing is compared while splitting. All the ordering happens in the merges, and a merge is cheap precisely because both halves are already sorted — only the two fronts can ever compete. log n levels × O(n) per level is the whole complexity argument, visible as the depth counter.
The statement says sort and the constraints say n up to 10⁵ — that alone rules out the quadratic three. When it also needs to be stable, or the data is a linked list, or you need a guaranteed bound rather than an average one, merge sort is the specific answer.
Split the range in half until each piece holds one element, which is sorted by definition. Then merge pairs of sorted ranges back together. A merge is linear because both inputs are already ordered, so only their two front elements can compete — and there are log n levels of merging, each doing O(n) work.
// Merge sort: nothing is compared on the way DOWN. All the ordering // happens in merge(), which is cheap because both halves are sorted. void merge(vector<int>& a, int low, int mid, int high) { vector<int> temp; int i = low, j = mid + 1; while (i <= mid && j <= high) temp.push_back(a[i] <= a[j] ? a[i++] : a[j++]); // <= keeps it STABLE while (i <= mid) temp.push_back(a[i++]); while (j <= high) temp.push_back(a[j++]); for (int k = 0; k < (int)temp.size(); k++) a[low + k] = temp[k]; // low + k, NOT k -- the offset is the bug } void mergeSort(vector<int>& a, int low, int high) { if (low >= high) return; // 0 or 1 elements int mid = low + (high - low) / 2; // not (low+high)/2 -- overflow mergeSort(a, low, mid); mergeSort(a, mid + 1, high); merge(a, low, mid, high); }
// Merge sort: nothing is compared on the way DOWN. All the ordering // happens in merge(), which is cheap because both halves are sorted. void merge(int[] a, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; while (i <= mid && j <= high) temp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps it STABLE while (i <= mid) temp[k++] = a[i++]; while (j <= high) temp[k++] = a[j++]; for (int x = 0; x < temp.length; x++) a[low + x] = temp[x]; // temp starts at 0, a starts at low } void mergeSort(int[] a, int low, int high) { if (low >= high) return; int mid = low + (high - low) / 2; mergeSort(a, low, mid); mergeSort(a, mid + 1, high); merge(a, low, mid, high); // the work is here, on the way UP }
# Merge sort: nothing is compared on the way DOWN. All the ordering # happens in merge(), which is cheap because both halves are sorted. def merge(a, low, mid, high): temp = [] i, j = low, mid + 1 while i <= mid and j <= high: if a[i] <= a[j]: # <= keeps it STABLE temp.append(a[i]); i += 1 else: temp.append(a[j]); j += 1 temp.extend(a[i:mid + 1]) temp.extend(a[j:high + 1]) a[low:high + 1] = temp # slice assignment carries the offset for you def merge_sort(a, low, high): if low >= high: # 0 or 1 elements return mid = (low + high) // 2 # Python ints do not overflow merge_sort(a, low, mid) merge_sort(a, mid + 1, high) merge(a, low, mid, high)
Copying the temp array back as a[i] = temp[i] instead of a[low + i] is the mistake that passes your own test. The very first merge has low == 0, so a small example sorts perfectly and every later subarray gets dumped at the front of the array. Also compute mid as lo + (hi - lo) / 2: (lo + hi) overflows a 32-bit int once the indices get large, and that bug lived in the JDK for nine years.
The walkthrough for #04 Merge Sort. Watch it, then go straight back and write it yourself.
“Count the pairs where i < j but a[i] > a[j].” Counting pairs is O(n²) by definition, so the constraint n ≤ 10⁵ is telling you the pairs must be counted in groups rather than one at a time — and “out of order” plus “grouped” means merge sort.
An inversion is a pair that a sort would have to swap past each other. Bubble sort makes exactly one adjacent swap per inversion, which is why it is O(n²) — it pays one operation per pair. Merge sort's merge can settle many at once: when you take a value from the right half, every element still left in the left half is greater than it and comes before it, so all of them form an inversion with it. Add mid - i + 1 in one go.
// Count Inversions = merge sort with a counter. The SORT is unchanged; // only the merge learns to count, and it counts in groups. long long merge(vector<int>& a, int low, int mid, int high) { vector<int> temp; int i = low, j = mid + 1; long long inv = 0; // 32-bit overflows: max is ~5e9 while (i <= mid && j <= high) { if (a[i] <= a[j]) { temp.push_back(a[i++]); // in order -- nothing to count } else { inv += (mid - i + 1); // ALL of the left half beats a[j] temp.push_back(a[j++]); } } while (i <= mid) temp.push_back(a[i++]); while (j <= high) temp.push_back(a[j++]); for (int k = 0; k < (int)temp.size(); k++) a[low + k] = temp[k]; return inv; } long long countInv(vector<int>& a, int low, int high) { if (low >= high) return 0; int mid = low + (high - low) / 2; long long inv = countInv(a, low, mid); inv += countInv(a, mid + 1, high); inv += merge(a, low, mid, high); // pairs SPANNING the two halves return inv; }
// Count Inversions = merge sort with a counter. The SORT is unchanged; // only the merge learns to count, and it counts in groups. long merge(int[] a, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; long inv = 0; // int overflows: max is ~5e9 while (i <= mid && j <= high) { if (a[i] <= a[j]) temp[k++] = a[i++]; // in order: nothing to count else { inv += (mid - i + 1); // a[i..mid] ALL beat a[j], in bulk temp[k++] = a[j++]; } } while (i <= mid) temp[k++] = a[i++]; while (j <= high) temp[k++] = a[j++]; for (int x = 0; x < temp.length; x++) a[low + x] = temp[x]; return inv; }
# Count Inversions = merge sort with a counter. The SORT is unchanged; # only the merge learns to count, and it counts in groups. def merge(a, low, mid, high): temp = [] i, j = low, mid + 1 inv = 0 # Python ints never overflow while i <= mid and j <= high: if a[i] <= a[j]: temp.append(a[i]); i += 1 # in order -- nothing to count else: inv += mid - i + 1 # ALL of the left half beats a[j] temp.append(a[j]); j += 1 temp.extend(a[i:mid + 1]) temp.extend(a[j:high + 1]) a[low:high + 1] = temp return inv def count_inv(a, low, high): if low >= high: return 0 mid = (low + high) // 2 inv = count_inv(a, low, mid) inv += count_inv(a, mid + 1, high) inv += merge(a, low, mid, high) # pairs SPANNING the two halves return inv
Adding 1 instead of mid - i + 1 is the wrong answer that looks careful — it counts one inversion per merge step rather than per pair, and on small examples the two numbers can even coincide. The other one: the answer can reach n(n−1)/2, which for n = 10⁵ is about 5 × 10⁹ and overflows a 32-bit int. Use long long.
The walkthrough for #08 Count Inversions. Watch it, then go straight back and write it yourself.
No new algorithm here and no new complexity — the same two sorts you already know, with the outer loop written as recursion. It is worth doing once because it is the cleanest example of a mechanical transformation you will use constantly in DP: a loop variable becomes a parameter, and the loop's exit becomes the base case.
WHAT ACTUALLY CHANGES WHEN A LOOP BECOMES RECURSION?
Converting bubble sort's outer loop to recursion. What becomes the base case?
Pass size 1. The loop ran for (i = n-1; i > 0; i--), so it stopped when i reached 1 — and that condition, inverted, is the base case: if (n == 1) return;. That is the whole mechanical rule. The early-exit on a clean pass is a second, separate return, and it is an optimisation rather than the base case — conflating the two is how the conversion goes wrong.
Recursive bubble sort and iterative bubble sort — how do their complexities compare?
Time is identical; space is not. Exactly the same comparisons and swaps happen in exactly the same order — the recursion is only bookkeeping. But each pending call keeps a stack frame, so n nested calls cost O(n) stack where the loop cost nothing. This is a real trade-off to be able to state, and it is why the recursive form is a teaching device rather than an improvement.
Recursive bubble sort that overflows the stack on every input. Which line is at fault?
void bubble(vector<int>& a, int n) { if (n == 1) return; for (int j = 0; j < n - 1; j++) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]); bubble(a, n); }
bubble(a, n - 1). Recursion needs the argument to move toward the base case; calling with the same n re-runs an identical pass forever. It is the single most common recursion bug and the reason to state the rule as one sentence: every recursive call must make the problem strictly smaller. The pass itself is correct — only the argument is.
Both algorithms split and recurse, so the split is not what separates them. Merge chooses its halves by position and does nothing on the way down — all the work is the combine, after both calls return, which is why it needs O(n) scratch. Quick partitions by value first, so the pivot reaches its final slot on the way down and there is nothing left to do coming back — which is why it sorts in place.
Not a new problem — bubble sort with the outer loop expressed as recursion. The signal to read is the transformation itself: a loop whose variable only ever shrinks is a recursion parameter waiting to happen.
One pass of bubble sort drives the largest value of the first n elements to index n−1. That is exactly the work the outer loop did once per iteration. So do one pass, then ask the function to sort the first n−1 elements. The inner loop does not change at all.
// Bubble sort with the OUTER loop as recursion. The inner loop is // untouched -- recursion replaces one loop, never both. void bubbleSort(vector<int>& a, int n) { if (n == 1) return; // the loop's exit, inverted bool didSwap = false; for (int j = 0; j < n - 1; j++) // one full pass, exactly as before if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); didSwap = true; } if (!didSwap) return; // early exit survives the rewrite bubbleSort(a, n - 1); // n - 1: the problem MUST shrink }
// Bubble sort with the OUTER loop as recursion. The inner loop is // untouched -- recursion replaces one loop, never both. void bubbleSort(int[] a, int n) { if (n == 1) return; // the loop's exit, inverted boolean didSwap = false; for (int j = 0; j < n - 1; j++) // one full pass, exactly as before if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; didSwap = true; } if (!didSwap) return; // the same early exit bubbleSort(a, n - 1); // SHRINK: the tail is final }
# Bubble sort with the OUTER loop as recursion. The inner loop is # untouched -- recursion replaces one loop, never both. def bubble_sort(a, n): if n == 1: # the loop's exit, inverted return did_swap = False for j in range(n - 1): # one full pass, exactly as before if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] did_swap = True if not did_swap: # early exit survives the rewrite return bubble_sort(a, n - 1) # n - 1: the problem MUST shrink
Recursing with the same n is an instant stack overflow, and it is easy to write because the pass itself looks complete. The subtler cost is the one people forget to mention in interviews: this version is O(n) space, not O(1). The recursion buys readability, not efficiency — say so before you are asked.
Insertion sort with the outer loop as recursion. Same transformation as the previous problem, applied to the algorithm whose inner loop is a shift rather than a swap — so the thing that changes is again only the outer structure.
Insertion sort's invariant is that a[0..i-1] is sorted. Recursively sort the first i elements, then insert a[i] into that sorted prefix by shifting. The recursion runs forwards, not backwards: you must sort the smaller prefix before you can insert into it.
// Insertion sort with the OUTER loop as recursion. Note the direction: // this counts UP toward n, because the prefix must be sorted first. void insertionSort(vector<int>& a, int i, int n) { if (i == n) return; // every index inserted int key = a[i]; // lift it out, leaving a gap int j = i - 1; while (j >= 0 && a[j] > key) { // '>' not '>=' -- keeps it STABLE a[j + 1] = a[j]; // shift right; the gap moves left j--; } a[j + 1] = key; // drop into the gap insertionSort(a, i + 1, n); // i + 1: forwards, not backwards }
// Insertion sort with the OUTER loop as recursion. Note the direction: // this counts UP toward n, because the prefix must be sorted first. void insertionSort(int[] a, int i, int n) { if (i == n) return; // every index inserted int key = a[i]; // lift it out, leaving a gap int j = i - 1; while (j >= 0 && a[j] > key) { // '>' not '>=' -- keeps it STABLE a[j + 1] = a[j]; j--; } a[j + 1] = key; insertionSort(a, i + 1, n); // GROW the sorted prefix }
# Insertion sort with the OUTER loop as recursion. Note the direction: # this counts UP toward n, because the prefix must be sorted first. def insertion_sort(a, i, n): if i == n: # every index inserted return key = a[i] # lift it out, leaving a gap j = i - 1 while j >= 0 and a[j] > key: # '>' not '>=' -- keeps it STABLE a[j + 1] = a[j] # shift right; the gap moves left j -= 1 a[j + 1] = key # drop into the gap insertion_sort(a, i + 1, n) # i + 1: forwards, not backwards
This one recurses upward — i + 1 toward n — where recursive bubble sort recursed downward toward 1. Copying the previous problem's shape and decrementing gives you a function that inserts into a prefix it has not sorted yet, and the result is subtly out of order rather than obviously broken.
Quick sort throws away merge sort's one expensive habit: there is no combine step at all. Partition alone does everything, by driving a single value to the position it will occupy in the final array — and once a pivot lands, it is never examined again. That is what buys O(1) extra space.
CAN YOU SORT BY DIVIDING, WITHOUT EVER MERGING BACK?
Partition has just finished. What is guaranteed about the pivot?
Its exact final position. Everything to its left is ≤ it and everything to its right is > it, so no future operation can have any reason to move it — and the recursion is deliberately written to exclude it, qs(lo, j-1) and qs(j+1, hi). Getting this is what makes it obvious why there is no merge step: each call leaves its own slot permanently correct, so there is nothing left to combine.
Partition [7, 2, 9, 4, 1, 8, 3, 6] with the leftmost element as pivot. What index does 7 end up at?
Index 5. You do not need to simulate the pointer dance to know this — just count how many values are smaller than the pivot: 2, 4, 1, 3 and 6, which is five. So five values must sit to its left and 7 lands at index 5, giving [3, 2, 6, 4, 1, 7, 8, 9]. The pivot's final index is always the count of values below it — a fast sanity check on any partition you write.
You hand quick sort an already-sorted array of 10⁵ elements, using the first element as pivot. What happens?
O(n²), and the recursion goes n deep. The pivot is the smallest element every single time, so partition puts nothing on its left and everything on its right — the array shrinks by one per call instead of halving. This is the case the lecture warns about, and it is genuinely nasty because sorted or nearly-sorted input is common in the real world. The fix is one line: pick a random pivot, or median-of-three, and swap it to the front.
No merge step exists. Partition alone does the work: when the two scans meet, the pivot swaps into place and is never examined again — everything left of it is smaller, everything right is larger. That is what buys O(1) extra space where merge sort needs O(n).
Sorting wanted in place, with no extra array allowed, and an average rather than guaranteed bound is acceptable. Also the giveaway for the whole family: any problem that only needs one element in its final position — kth largest, median — wants partition, not a full sort.
Choose a pivot. Rearrange the range so everything ≤ pivot sits left of it and everything greater sits right. The pivot is now exactly where it belongs and can be ignored forever. Recurse on the two sides. Because each call fixes its own pivot in place, there is nothing to merge afterwards.
// Quick sort: no combine step at all. Partition drives ONE value to its // final slot, and that slot is never touched again. int partition(vector<int>& a, int low, int high) { int pivot = a[low], i = low, j = high; while (i < j) { while (i < high && a[i] <= pivot) i++; while (j > low && a[j] > pivot) j--; if (i < j) swap(a[i], a[j]); } swap(a[low], a[j]); // the pivot lands, FOR GOOD return j; } void quickSort(vector<int>& a, int low, int high) { if (low >= high) return; int p = partition(a, low, high); quickSort(a, low, p - 1); // p is excluded from both sides -- quickSort(a, p + 1, high); // it is already final }
// Quick sort: no combine step at all. Partition drives ONE value to its // final slot, and that slot is never touched again. int partition(int[] a, int low, int high) { int pivot = a[low], i = low, j = high; while (i < j) { while (i < high && a[i] <= pivot) i++; while (j > low && a[j] > pivot) j--; if (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; } } int t = a[low]; a[low] = a[j]; a[j] = t; // the pivot lands for good return j; } void quickSort(int[] a, int low, int high) { if (low >= high) return; int p = partition(a, low, high); quickSort(a, low, p - 1); // no merge afterwards quickSort(a, p + 1, high); }
# Quick sort: no combine step at all. Partition drives ONE value to its # final slot, and that slot is never touched again. def partition(a, low, high): pivot, i, j = a[low], low, high while i < j: while i < high and a[i] <= pivot: i += 1 while j > low and a[j] > pivot: j -= 1 if i < j: a[i], a[j] = a[j], a[i] a[low], a[j] = a[j], a[low] # the pivot lands, FOR GOOD return j def quick_sort(a, low, high): if low >= high: return p = partition(a, low, high) quick_sort(a, low, p - 1) # p is excluded from both sides -- quick_sort(a, p + 1, high) # it is already final
Using the first element as pivot makes already-sorted input the worst case: every partition splits into 0 and n−1, giving O(n²) and a recursion n deep that will overflow the stack at 10⁵. Sorted input is common in practice, so this is not a theoretical concern. Randomise the pivot — or take median-of-three — and swap it to lo before partitioning, and the whole failure mode disappears for one line.
The walkthrough for #07 Quick Sort. Watch it, then go straight back and write it yourself.
Every unit so far produced order. These two consume it. In both, sorting is not the answer — it is the move that makes an O(n²) problem collapse into a single pass, and recognising that is worth more than any one algorithm in this deck.
WHEN IS SORTING THE SETUP RATHER THAN THE ANSWER?
In the Dutch national flag partition, a[mid] is 2 and you swap it with a[high]. Does mid advance?
No, and this is the entire bug surface of the problem. When you swap with low you know what comes back — everything before mid is already classified, so it must be a 1 and mid can safely advance. But high is the unexamined region: the value it hands you has never been looked at, so it must be classified next. Advance mid there and you skip an element, and the array comes out almost sorted — the worst kind of wrong.
Merge Intervals sorts by start time. Why not by end time?
Sorting by start gives you the property the whole sweep rests on: once you are at interval i, every earlier interval starts before it, so if it overlaps anything it must overlap the most recently kept one. That turns “does this overlap any of the others?” — an all-pairs question — into a single comparison against out.back(). Sorting by end can also be made to work, but it is the natural key for a different problem: maximum non-overlapping intervals.
Merge Intervals. On [[1,3],[2,6],[8,10],[15,18],[16,17]] this returns [[1,6],[8,10],[15,17]] instead of [[1,6],[8,10],[15,18]]. Which line?
if (!out.empty() && cur[0] <= out.back()[1]) out.back()[1] = cur[1]; else out.push_back(cur);
max(out.back()[1], cur[1]). [16,17] sits entirely inside [15,18], so it overlaps — but assigning its end blindly pulls 18 back to 17 and silently loses an hour of coverage. It never crashes and the output still looks like a plausible list of merged intervals, which is what makes it expensive. Step the visualiser to the last interval and watch the kept bar deliberately not shrink.
Three pointers carve the array into 0s done · 1s done · never looked at · 2s done. The move that everyone gets wrong is the last one: when a 2 goes to the back, mid does not advance — the value dragged in from high has never been classified. Step it and watch mid stall.
Unsorted, any interval can overlap any other and you are looking at O(n²) pairs. Sorted by start, an overlap can only ever be with the interval you just kept — so one comparison per interval settles it. That collapse from all-pairs to one sweep is what sorting actually bought you.
Only three distinct values, and the follow-up asks for one pass with constant space. Three buckets plus “one pass” is the Dutch national flag, every time. The counting-sort answer is the one the interviewer expects you to give first and then beat.
Maintain three regions with three pointers: everything before low is 0, everything between low and mid is 1, everything after high is 2, and the stretch from mid to high is unexamined. Look at a[mid] and send it to the region it belongs in, shrinking the unknown stretch by one each time — except when it goes to the back, because then you have pulled in something you have never seen.
// Dutch national flag: three regions, one pass, no counting. // The asymmetry between the two swaps is the whole problem. void sortColors(vector<int>& a) { int low = 0, mid = 0, high = a.size() - 1; while (mid <= high) { if (a[mid] == 0) { swap(a[low], a[mid]); low++; mid++; // safe: a[low] was a known 1 } else if (a[mid] == 1) { mid++; // already in the middle region } else { swap(a[mid], a[high]); high--; // mid does NOT move -- the value } // from high has never been seen } }
// Dutch national flag: three regions, one pass, no counting. // The asymmetry between the two swaps is the whole problem. void sortColors(int[] a) { int low = 0, mid = 0, high = a.length - 1; while (mid <= high) { if (a[mid] == 0) { int t = a[low]; a[low] = a[mid]; a[mid] = t; low++; mid++; // safe: a[low] was a known 1 } else if (a[mid] == 1) { mid++; // already in the middle region } else { int t = a[mid]; a[mid] = a[high]; a[high] = t; high--; // mid does NOT move: the value is unseen } } }
# Dutch national flag: three regions, one pass, no counting. # The asymmetry between the two swaps is the whole problem. def sort_colors(a): low, mid, high = 0, 0, len(a) - 1 while mid <= high: if a[mid] == 0: a[low], a[mid] = a[mid], a[low] low += 1; mid += 1 # safe: a[low] was a known 1 elif a[mid] == 1: mid += 1 # already in the middle region else: a[mid], a[high] = a[high], a[mid] high -= 1 # mid does NOT move -- the value # from high has never been seen
Advancing mid after swapping a 2 to the back is the bug in this problem. Swapping with low is safe — the region before mid is already classified, so what comes back is known to be a 1. Swapping with high hands you a value from the unexamined region, and if you skip it you leave a 0 stranded on the right. The array comes back almost sorted, which is much harder to spot than a crash.
Intervals, and a question about overlap. Unsorted, overlap is an all-pairs question and therefore O(n²). The instant you are allowed to reorder them, sort by start and the question becomes local: does this one touch the last one I kept?
Sort by start time. Walk left to right holding a single “current” interval. Because the starts are ordered, no interval you have already passed can possibly reach further right than the one you are holding — so if the next interval overlaps anything at all, it overlaps that one. Extend it, or close it off and start a new one.
// Sorting is the SETUP here, not the answer: it makes "does this overlap // anything?" into "does this touch the one interval I am holding?". vector<vector<int>> merge(vector<vector<int>>& a) { sort(a.begin(), a.end()); // by start -- this is the whole trick vector<vector<int>> out; for (auto& cur : a) { if (!out.empty() && cur[0] <= out.back()[1]) // <= : touching counts out.back()[1] = max(out.back()[1], cur[1]); // max: [16,17] inside else // [15,18] must NOT out.push_back(cur); // shrink it } return out; }
// Sorting is the SETUP here, not the answer: it makes 'does this overlap // anything?' into 'does this touch the one interval I am holding?'. public int[][] merge(int[][] a) { Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0])); // by start List<int[]> out = new ArrayList<>(); for (int[] cur : a) { if (!out.isEmpty() && cur[0] <= out.get(out.size() - 1)[1]) { int[] last = out.get(out.size() - 1); last[1] = Math.max(last[1], cur[1]); // max: a nested one cannot shrink it } else { out.add(new int[]{cur[0], cur[1]}); // real gap } } return out.toArray(new int[0][]); }
# Sorting is the SETUP here, not the answer: it makes "does this overlap # anything?" into "does this touch the one interval I am holding?". def merge(a): a.sort() # by start -- this is the whole trick out = [] for cur in a: if out and cur[0] <= out[-1][1]: # <= : touching counts out[-1][1] = max(out[-1][1], cur[1]) # max: [16,17] inside else: # [15,18] must NOT shrink it out.append(list(cur)) return out
Writing kept.end = cur.end instead of max(kept.end, cur.end) breaks only when an interval is fully contained in the one you are holding — [15,18] then [16,17] comes back as [15,17]. It never crashes, it is still a valid-looking list of intervals, and most hand-written test cases miss it. Also use <=, not <: [1,3] and [3,5] touch at a point and almost every judge counts that as overlapping.
A binary tree with no pointers and no allocation: the children of index i are 2i+1 and 2i+2, so a flat array is a heap if you agree to read it as one. That single reinterpretation buys you the guaranteed O(n log n) that quick sort cannot promise, in O(1) space that merge sort cannot promise.
WHAT IF THE ARRAY WERE ALREADY A TREE?
Building a max heap from an unsorted array of n elements costs what?
O(n), and this is the result the lecture spends real time deriving because it looks wrong. Sifting down is only expensive for nodes near the top, and there are almost none of them: half the nodes are leaves and cost nothing, a quarter can sift at most one level, an eighth at most two. The sum ∑ n/2^(k+1) · k converges to n. Inserting one at a time genuinely is O(n log n) — the backwards build is what saves you.
The array is [7, 2, 9, 4, 1, 8, 3, 6] read as a heap. Which elements are the children of index 1?
Indices 3 and 4, holding 4 and 1. The rule is 2i+1 and 2i+2, so index 1 has children at 3 and 4. Nothing about this array is a tree in memory — the tree exists entirely in the arithmetic, which is exactly why heap sort needs no extra space. Check the reverse too: the parent of index 4 is (4−1)/2 = 1.
Why does building the heap start at index n/2 − 1 rather than at 0 or at n − 1?
Everything from n/2 onward is a leaf, and a single node is already a valid heap — sifting it down does nothing. So the build starts at the last node that actually has children and walks backwards. Starting at 0 instead is not wrong so much as useless: sifting the root before its subtrees are heaps does not establish the property, which is why the direction has to be bottom-up.
No pointers and no extra array: the children of index i are 2i+1 and 2i+2, so a flat array is a binary tree. Build a max heap, then repeatedly swap the root to the end and shrink. O(n log n) guaranteed — the worst case quick sort cannot promise.
Every algorithm so far is stuck at n log n for one reason: they all ask is a < b?, and answering that question n log n times is provably unavoidable. This one never asks. It uses the value itself as an array index — and an index lookup is not a comparison, so the lower bound simply does not apply to it.
IS n log n REALLY A LOWER BOUND FOR SORTING?
Comparison sorts cannot beat O(n log n). How does counting sort get O(n + k)?
It is not a comparison sort at all, so the theorem simply does not cover it. The n log n bound comes from a decision-tree argument: with only yes/no comparisons you need at least log₂(n!) ≈ n log n of them to distinguish n! possible orderings. Counting sort sidesteps the whole argument by asking a different kind of question — where does this value live? — which an array index answers in O(1).
You must sort 1000 integers, each between 0 and 1,000,000,000. Counting sort?
No. O(n + k) is linear in n + k, not in n, and here k dwarfs n by six orders of magnitude — you would allocate a billion-entry array to sort a thousand numbers. The rule to carry away: counting sort wins when k is comparable to n (ages, exam scores, the 0/1/2 of Sort Colors) and is a catastrophe otherwise. This is exactly the case radix sort was invented to rescue.
What makes the prefix-sum version of counting sort stable?
The prefix sums turn each count into “the position just past where this value's block ends”. Walking the input from the right and decrementing that position as you place each element means the last equal element is placed last, so the original order among equals survives. It matters far more than it looks: radix sort is only correct because its inner sort is stable, which is the next unit.
Every algorithm above is stuck at n log n because they all ask is a < b?. This one never asks. It uses the value itself as an array index, so it escapes the comparison lower bound entirely — at the price of needing the values to be small integers.
Counting sort's fatal flaw is a large value range. Radix sort fixes it by refusing to look at whole values at all: sort by the last digit, then the next, and so on. Each pass has a range of only ten — and the reason the whole thing works is that each pass is stable, so it preserves the order the previous pass established.
HOW DO YOU KEEP COUNTING SORT'S SPEED WHEN THE VALUES ARE HUGE?
Radix sort's per-digit pass must be stable. What breaks if it is not?
The whole thing collapses. After the units pass, two numbers with the same tens digit are already correctly ordered relative to each other. The tens pass sees them as equal — and if it is allowed to reorder equal elements, it throws away the work the units pass just did. Stability is what makes the passes compose rather than overwrite. That is why the previous unit's prefix-sum detail mattered.
Why sort by the LEAST significant digit first rather than the most?
Going least-significant-first, every pass is a single flat stable sort over the whole array, and the result is correct after the last one — no recursion, no bookkeeping. Most-significant-first is not wrong, but once you have split on the top digit you must sort each bucket independently, which means recursion and separate sub-arrays. LSD is chosen because it is the flat, iterative version.
Sorting 10⁶ integers up to 10⁹ in base 10. How does radix compare with an O(n log n) sort?
This is the honest answer and the one worth being able to give. d = 10 digits, so radix does 10 passes ≈ 10⁷ element-moves; a comparison sort does about n log₂n ≈ 2 × 10⁷ comparisons. The same ballpark — and in practice std::sort often wins anyway because it is cache-friendly while radix scatters writes across buckets. “Linear” hides a constant factor of d, and d grows with the value range.
Counting sort run once per digit, starting with the least significant, which looks backwards until you see why. Each pass must be stable: values sharing a digit keep the order the previous pass gave them, so a later pass on a higher digit never destroys the work of the lower ones. Drop stability and the whole scheme collapses. Not one comparison between two values, anywhere.
Insertion sort is superb on nearly-ordered input and terrible otherwise, because a value can only ever move one slot per shift. Shell sort's fix is almost impudent: run insertion sort on elements spaced a gap apart, so a badly placed value can leap most of the array in one move — then shrink the gap. The final pass is ordinary insertion sort, on input that is now nearly ordered.
CAN YOU MAKE INSERTION SORT'S BEST CASE HAPPEN ON PURPOSE?
What is shell sort actually doing on each pass?
Insertion sort, on gapped subsequences. The code is literally insertion sort with j-- replaced by j -= gap — that one change is the whole algorithm. With gap = 4 on eight elements you are insertion-sorting {0,4}, {1,5}, {2,6} and {3,7} independently. Seeing it as “insertion sort with a stride” makes it something you can reconstruct rather than memorise.
Why do the large-gap passes help, when the final gap = 1 pass has to run anyway?
Insertion sort's cost is essentially the number of inversions, and its weakness is that each shift removes exactly one. A gap pass moves a value many positions in a single step, killing many inversions at once. By the time gap reaches 1 the array is nearly ordered, which is precisely insertion sort's O(n) best case — so shell sort is insertion sort that manufactures its own best case first.
Shell sort is stable, like the insertion sort it is built from. True or false?
False, and it is a genuinely surprising loss. Each individual gapped pass is stable within its own subsequence, but the subsequences are interleaved: a value can be lifted over an equal value that sits in a different subsequence entirely, and no later pass restores the original order. Building a stable algorithm out of stable parts does not give you a stable whole — which is exactly why radix sort had to be so careful.
Insertion sort is slow for one reason: a value can only move a single slot per swap. Shell fixes exactly that by comparing across a gap, so a badly-placed element travels a long way in one move. The gaps shrink, and the final pass at gap 1 is insertion sort — but on an array that is already nearly sorted, which is insertion's best case rather than its worst.
Every bound in this deck is derived, not memorised. Three arguments, and the third is the one worth carrying out of here.
Pass 1 looks at n−1 elements, pass 2 at n−2, and so on to 1. That sum is n(n−1)/2 — the triangle number — which is n²/2 once you drop the constant.
It is fixed for selection because the scan never stops early. Bubble and insertion can finish in O(n) only because their inner loop has a data-dependent exit.
Halving until you reach single elements takes log₂ n levels. Every level touches all n elements exactly once — merging them, or partitioning them.
log n levels × O(n) per level. Quick sort only reaches this when the pivot splits evenly; a degenerate pivot gives n levels instead of log n, and you are back to n².
n elements have n! possible orders. Each comparison is one yes/no, so k comparisons distinguish at most 2ᵏ cases. You need 2ᵏ ≥ n!, giving k ≥ log₂(n!) ≈ n log n.
Note what the proof assumes: that you only ever compare. Counting and radix sort never do — they use the value as an index. The theorem is untouched; it simply does not apply to them.
Not one of these crashes. Every one returns a plausible array and a wrong answer — which is exactly what makes them cost an hour instead of a minute.
Set true by the first swap and never reset, so the early exit can never fire and the O(n) best case silently reverts to O(n²). The answer stays correct, which is why nobody notices.
a[i] = temp[i] instead of a[low + i]. The first merge has low = 0 so a small test passes perfectly, and every later subarray lands at the front.
First-element pivot makes already-sorted data the worst case, not the best: O(n²) and a recursion n deep. Sorted input is common, so this is a real failure, not a theoretical one.
inv++ instead of inv += mid - i + 1 counts one per merge step rather than per pair. On small examples the two can even agree. The total also overflows a 32-bit int at n = 10⁵.
In the Dutch flag, the value pulled back from high has never been classified. Skip it and a 0 is stranded on the right — the array comes back almost sorted.
kept.end = cur.end breaks only for a fully contained interval: [15,18] then [16,17] returns [15,17]. Still a valid-looking list, and most hand-written tests miss it.
A problem needs the array sorted AND guarantees no worse than O(n log n), on 10⁶ elements, with memory tight. Which do you reach for?
Heap sort is the only one that gives you both. Quick sort is usually fastest but can degrade to O(n²); merge sort has the guarantee but wants O(n) extra memory, which the constraint rules out; counting sort needs a small value range that nobody promised. This is the trade-off the whole deck exists to make automatic.
Which pair of algorithms escapes the O(n log n) comparison lower bound entirely?
Counting and radix. The bound is a theorem about algorithms that learn only through is a < b?; both of these use the value itself as an index and never ask. That is not a loophole, it is a different model — and it is the single best idea in the topic, which is why the deck teaches it even though the sheet does not.
A problem says: 10⁵ meeting times, report how many overlap. What is your first move?
Sort, then sweep. All-pairs on 10⁵ is 10¹⁰ and hopeless; sorting costs 10⁵ log 10⁵ and then makes overlap a local question — you only ever compare against the interval you are holding. That reframing is unit 05's whole lesson and it generalises far past intervals: sorting is often the setup, not the answer.
The slide to reopen the night before: every algorithm in this deck, what it costs, and the sentence in the statement that selects it.
Nine units, 10 problems, and one idea underneath all of it: n log n is a floor only for algorithms that ask “is a < b?” If you remember two things, make them that — and that sorting is very often the setup rather than the answer.
Lectures 1–3 are Striver's A2Z course; lectures 4–7 are Abdul Bari's sorting series. Problem links are GeeksforGeeks practice and LeetCode.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.