Practice question · Multiple choice
Stability in a sort, preserving the order of equal elements, sounds like a technicality. When does it become essential?
Hints
- Ask how you would produce a list sorted by department and then by name within each.
- What does an unstable sort do to the work of the previous pass?
Show the answer
A. When sorting by successive keys, so earlier order survives
Why
Multi-key sorting is built on it: sort by the secondary key, then stably by the primary, and the earlier order survives inside each group. An unstable sort discards that work, which is why Python's sort is guaranteed stable and why spreadsheet sorting behaves the way users expect.
Practise Sorting Strategies
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Sorting Strategies
- Order the steps of one round of selection sort.
- Sorting stability only matters when the records carry information beyond the key being sorted on.
- Sort each sorting algorithm by its typical asymptotic cost.
- Comparison-based sorting cannot beat O(n log n), and counting sort runs in O(n). Why is that not a…
- Match each sort to its distinguishing property.