Card 07/ 08
Practice: Picking the Sort for Four Programs
A leaderboard, a merged log, a microcontroller and exam marks: name the constraint that decides each sort.
Picking a sort means finding the one constraint in a program that rules the others out, then choosing the sort that meets it. This exercise practises that on four programs, each with a different deciding constraint.
- A leaderboard of 10,000 scores is kept sorted from highest to lowest. After each round, three players' scores rise, and the board must be re-sorted.
- A combined log. A day's events from several servers are gathered into one list and sorted by timestamp. Events with the same timestamp must stay in the order they were written, because a later event can depend on an earlier one.
- A microcontroller sorts 2,000 readings to find a percentile, has no memory left beyond the readings, and must answer within a fixed time on every input.
- Exam marks, whole numbers from 0 to 100, for 5,000 students, sorted to publish rank order.
For each program, name the constraint that decides, the sort it leads to, and whether you would write the sort or call a built-in one.
Show a sort for each program
| Program | Constraint that decides | Sort | Call |
|---|---|---|---|
| Leaderboard | Nearly sorted after each round | Insertion sort | The built-in sort in Python or Java, which adapts to sorted runs; or a hand-written insertion sort |
| Combined log | Equal timestamps must keep their order | A stable sort: merge sort | The built-in sort with a key on the timestamp, stable in all three languages for objects |
| Microcontroller | No spare memory, and a worst case every input must meet | Heapsort | Hand-written, since the device has no library sort to call |
| Exam marks | Integer keys in a range of 101 values | Counting sort | Hand-written, with 101 counters |
The leaderboard is sorted except for three entries, and a run of insertion sort on 10,000 scores with three of them raised by 5,000 made 10,138 comparisons, against about 132,877 that n log₂ n predicts for a sort that ignores the existing order. Python's and Java's object sorts find the long runs too, so calling them is as good.
The log needs stability above everything, which rules out heapsort and quicksort; each language's built-in sort for objects is a stable merge sort and is the right call. Sorting by timestamp alone, with a stable sort, keeps each second's events in written order.
The microcontroller has the sensor buffer's constraints: no merge buffer, no deep stack, and no quadratic input allowed. Heapsort is the only sort in the subject that meets all three.
The exam marks are integers from 0 to 100, so k = 101 against n = 5,000, and counting sort runs in about n + k = 5,101 steps with 101 counters. A built-in comparison sort would also be fine at this size; counting sort is the one that exploits the keys, and it is stable when it places students from the last.
← → move through sections and cards