Practice question · Put in order
Order the steps of merge sort on [3, 1, 4, 2].
- Merge pairs: [1,3] and [2,4]
- Split further into [3],[1] and [4],[2]
- Split into [3,1] and [4,2]
- Merge final halves: [1,2,3,4]
Hints
- Splitting must finish before any merging can begin.
- The merge step combines pairs that are already in order.
Show the answer
- Split into [3,1] and [4,2]
- Split further into [3],[1] and [4],[2]
- Merge pairs: [1,3] and [2,4]
- Merge final halves: [1,2,3,4]
Why
Merge sort recursively splits, then merges sorted sub-arrays bottom-up.
Practise Searching and sorting ideas
The app has 8 more questions on this lesson, and keeps your place in the course. Physics I is free to start.
More questions on Searching and sorting ideas
- Trace selection sort on the list [7, 2, 9, 1]. Order the states the list passes through.
- Classify each sort as O(n²) average or O(n log n) average.
- You guess a number between 1 and 1000; after each guess you learn "higher" or "lower". A smart player needs…
- Binary search is far faster than linear search but is used less often in practice. Why is it used less often…
- Binary search finds a name among 1,000 sorted entries in ~10 steps. Estimate the steps needed for…