Algorithms from zero
Sorting and search: multiple-choice review
Crux Multiple-choice synthesis across the sorting and search unit: when sorting pays off, stability, merge vs quicksort tradeoffs, the binary-search invariant, and binary search on the answer.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. Each one is a decision you make when you reach for sorting or search in real code — not a definition to recite, but a tradeoff to weigh.
Goal
Confirm you can connect the unit’s spine: sorting is preprocessing you pay for once, the O(n log n) sorts trade stability against memory and worst-case behaviour, and binary search generalises from arrays to any monotonic answer space.
Quiz
Completed
You receive an unsorted array of 1,000,000 elements and need to answer exactly one membership query: is value X present? What is the cheapest correct approach?
Heads-up For a single query, O(n log n) sort plus O(log n) search is strictly worse than one O(n) scan. Sorting is preprocessing: it pays off only when amortised over many later queries.
Heads-up Building the set is still O(n), the same order as the scan, with extra memory and no benefit for one lookup. The point is that any preprocessing is wasted for a single query.
Heads-up Binary search requires a sorted array. On unsorted input it discards the wrong half and returns wrong answers — sortedness is its precondition.
Quiz
Completed
You sort a list of orders by amount, where several orders share the same amount, and you need ties to stay in their original arrival order. Which sort is safe?
Heads-up Speed has nothing to do with stability. Lomuto-partition quicksort can reorder equal keys when it swaps them across the pivot boundary; it is not stable.
Heads-up Selection sort is also unstable: swapping the minimum into place can leap an equal element over another, breaking arrival order. Insertion sort and merge sort are the stable choices.
Heads-up Stability is independent of complexity. Merge sort (O(n log n)) is stable; quicksort and heapsort (also O(n log n)) are not. You must pick the algorithm, not just the bound.
Quiz
Completed
Merge sort and quicksort are both O(n log n) on average. For sorting a huge array in place under tight memory, with no stability requirement, why is quicksort often the production choice?
Heads-up It is the reverse: merge sort is O(n log n) always, quicksort degrades to O(n²) on bad pivots. Quicksort wins on memory and constants, not on worst case.
Heads-up Merge sort is the stable one. Its O(n) merge buffer is the reason to prefer in-place quicksort here, not any stability problem.
Heads-up Quicksort is recursive too; it uses O(log n) stack on balanced partitions. The advantage is partitioning in place versus merge sort's O(n) auxiliary array.
Quiz
Completed
A quicksort that always picks the last element as pivot runs fine on random data but takes minutes on data that arrives already sorted. Why, and what is the standard fix?
Heads-up Comparisons cost the same; the problem is the partition shape. A fixed last-element pivot on sorted data is always extreme, producing maximally unbalanced O(n²) recursion.
Heads-up It sorts correctly — it is just slow. The output is right; the recursion is degenerate, turning O(n log n) into O(n²).
Heads-up There is no silent restart; deep recursion may overflow the stack, but the core issue is the O(n²) work from unbalanced partitions. Randomized pivots restore O(n log n) expected time.
Quiz
Completed
A binary search uses while (lo < hi) with hi set to arr.length - 1 and returns -1 after the loop. It works on most inputs but misses the target when it sits at the position where lo equals hi. What is the defect?
Heads-up With an inclusive range hi = arr.length - 1 is correct; using arr.length would read out of bounds. The bug is the strict < in the loop condition leaving the lo == hi cell unchecked.
Heads-up The rounding of mid is not the cause here; the loop simply terminates before inspecting the lo == hi index. Switch the condition to lo <= hi.
Heads-up It can, with a correct invariant. The miss is purely the off-by-one in the loop boundary, not a limitation of binary search.
Quiz
Completed
You need the minimum ship capacity to deliver all packages within D days, with no sorted array of capacities to index. When can you still binary search?
Heads-up Binary search needs a sorted/monotonic search space, not a literal array. A monotonic feasible() predicate lets you halve the answer range the same way.
Heads-up The weights' order is irrelevant; the feasibility check handles them as given. What must be monotonic is feasible(capacity) as capacity increases.
Heads-up That is exactly the non-monotonic case where binary search fails: a flip that reverses breaks the half-discarding logic. You need a single false-to-true transition.
Recap
The unit’s through-line is one habit: decide whether order is worth buying. Sort only when you reuse the order; pick a stable sort (merge, insertion) when ties must hold their place; trade merge sort’s O(n) buffer for quicksort’s in-place O(log n) stack when memory is tight, and accept that bad pivots risk O(n²) unless you randomize. Once order exists, binary search finds answers in O(log n) — but only with a correct inclusive invariant, and it generalises to any monotonic predicate, not just arrays.