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.
What a strong answer looks like
A strong Unit 7 answer compares on all three axes and names the input that triggers a worst case.
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.
Study move
Explain why the bound follows from the number of possible orderings.
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.
Study move
Trace quick sort on sorted input with a first-element pivot and count partitions.
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.
Study move
Sort records by two fields in sequence and show what instability would destroy.
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.
Study move
State the condition under which counting sort beats a comparison sort.
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.
