Practice question · Match the pairs
Match each sort to its distinguishing property.
- Merge sort
- Quicksort
- Insertion sort
- Heapsort
- Fast on average but O(n^2) with a bad pivot
- Always O(n log n) and stable
- Guaranteed O(n log n), sorts in place
- Beats the fancy sorts on small or nearly-sorted inputs
Hints
- Only one of these is both always-n-log-n and stable.
- One simple sort is genuinely the fastest choice on tiny inputs.
Show the answer
- Merge sort → Always O(n log n) and stable
- Quicksort → Fast on average but O(n^2) with a bad pivot
- Insertion sort → Beats the fancy sorts on small or nearly-sorted inputs
- Heapsort → Guaranteed O(n log n), sorts in place
Why
Merge sort is stable and always O(n log n); quicksort is fast but has an O(n^2) worst case; insertion sort wins on small or nearly-sorted data; heapsort guarantees O(n log n) in place.
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.
- Stability in a sort, preserving the order of equal elements, sounds like a technicality. When does it become…
- 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…