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 ready to merge
Count one level for each round of halving. How many levels does splitting sixteen values down to single items take?
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 2 5 7 with 1 6 8. 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 jumbled list that is out of order
- 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.
4 · Sixteen halves to 8, then 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 jumbled list that is out of order · 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.