core practice · coding problem
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.
The mechanism
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?).
Expected evidence
Equal scores keep input order: [a:5, b:3, c:5] -> [a:5, c:5, b:3]
Try this drill in the practice workspace →
Hints when you need them
- Decorate each row with its original index, then break ties on that index.
- A comparator returning 0 for ties does not guarantee stability in every runtime — make the tie-break explicit.
Watch for these 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