SME
Data Structures & Algorithms · Problem type
Merge sort pass by pass
Use this for “Show the passes of merge sort on 5 2 8 1 9 3 7 4. How many comparisons does it make?”
Put in order
Put the passes of merge sort in order, with the comparisons each one makes.
1
?
2
?
3
?
4
?
Assumptions
•
Each pass merges neighboring sorted runs into runs twice as long, so 8 items take log₂8 = 3 passes.
•
Merging compares the fronts of two runs and moves the smaller; it stops when one run is empty.
•
Merging runs of lengths a and b takes at most a + b − 1 comparisons, so a pass costs under n.
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Sorting and searching
Main lesson
Comparisons: quadratic sorts vs merge sort
Use this for “How many comparisons does selection sort make on 1000 items, and at most how many does merge sort make?”
Hash table probes
Use this for “750 keys sit in a hash table of 1000 slots. How many probes does a search take on average?”