DSA & Implementation · core
Sorting
Comparison sorts, stability, in-place versus extra space, and when a linear-time sort is available.
Mental model
Comparison sorting cannot beat O(n log n) because n! orderings need log2(n!) comparisons to distinguish — so a faster sort must stop comparing and exploit structure in the keys, which is what counting and radix sort do. The practical choice is rarely the asymptote: it is stability (does equal-key order survive?) and space (can you afford the merge buffer?).
How to study Sorting
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use MIT 6.006 — Lecture 3: Sets and Sorting, MIT 6.006 — Lecture 5: Linear Sorting, USACO Guide — Introduction to Sorting to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Sorting with Binary Search, Heap / Priority Queue, Intervals. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Stable sort by one key and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Sorting is the setup step for most interval, two-pointer, and greedy solutions — getting stability or the comparator wrong silently corrupts the result rather than crashing.
Common mistakes
- Assuming the language's sort is stable — it is in JS and Python, it is not for primitives in many others
- Sorting numbers with a default lexicographic comparator, so 10 sorts before 9
- Reaching for a linear-time sort without a bounded key range, where it is slower than comparison sorting
- Sorting inside a loop when one sort before the loop would do
Learn from primary sources
Practice and explain it back
Stable sort by one key
Implement sortByScore(rows) returning rows ordered by descending numeric `score`, with the original relative order preserved for equal scores (a stable sort). Do not mutate the input.
Expected evidence: Equal scores keep input order: [a:5, b:3, c:5] -> [a:5, c:5, b:3]
Open the interactive drill →Review prompts
- You sort records by score, then by date, expecting both orderings to hold. Why does this only work if the sort is stable, and what breaks if it is not?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.