Unit 7 · Moderate
A small set of algorithms used as a lens for comparing time, space, and stability. The comparison matters more than any single implementation.
Know
Any sort based on comparisons needs at least n log n comparisons in the worst case, because it must distinguish every possible ordering.
Apply
Use the bound to recognise when an algorithm claiming to beat it must be exploiting key structure.
Watch out
Believing a comparison sort can be linear in general. Only non-comparison methods escape the bound.
Know
Merge sort always splits evenly and is stable, at the cost of linear extra space. Quick sort partitions in place and is usually faster, but degrades on a poor pivot.
Apply
Choose merge sort for guarantees and stability, quick sort for average speed and memory.
Watch out
Recommending quick sort without mentioning pivot choice, which is what determines whether the worst case appears.
Know
Stability preserves the order of equal keys, which matters when sorting repeatedly on different fields. In-place means constant extra space.
Apply
When sorting on a secondary key first, require stability or the earlier sort is lost.
Watch out
Assuming a library sort is stable. It varies by language and implementation.
Know
Counting and radix sort index by key value rather than comparing, achieving linear time when keys are bounded integers.
Apply
Use counting sort when the key range is small relative to the number of items.
Watch out
Applying counting sort to a huge key range, where the memory cost exceeds any time saving.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Sort employee records by department and then by salary within department, and state the stability requirement that makes your approach correct.
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic