Sorting by splitting in half

Computing · Algorithms & Data Structures · ages 17-18

Name ______________________ Date ____________

When merging two sorted halves, which front value do you copy next?
- The larger front value
- A random front value
- The smaller front value
What is the base case of merge sort?
- A list of one item or none
- A list of eight items
- Two sorted halves
Splitting eight values down to single items takes how many levels?
Answer: ______________
Why does merge sort cost order n log n?
- Each of log n levels merges all n items
- It compares every pair twice
- It splits into n levels of one item
Merge 1 4 6 with 2 3 5. How many comparisons place all six items?
- 3
- 6
- 5
Order n log n beats order n squared badly once inputs grow large.
Circle one: True False
A student merges by always copying the larger front value. What results?
- A descending jumble instead of an ordered merge
- The same ordered merge, only faster
- A tree with three levels
About how many split levels does a list of a thousand need?
- About 3
- About 1000
- About 10

Answer key

For grown-ups. Fold this page away before handing over the rest.

The smaller front value · Copying the smaller available value keeps the result ordered.
A list of one item or none · One item or none needs no sorting at all.
3 · Eight halves to 4, then 2, then 1.
Each of log n levels merges all n items · Linear work per level times log n levels gives the total.
5 · Each comparison places one item, and this merge needs 5.
True · N log n grows far more slowly than n squared.
A descending jumble instead of an ordered merge · The two finger rule only orders when the smaller front goes first.
About 10 · A thousand is near 2 to the 10th, so about 10 halvings reach ones.