Practice question · Put in order
Order the steps of merge sort on a list.
- Sort the right half by the same method
- Sort the left half by the same method
- Return the merged list
- Merge the two sorted halves into one sorted list
- Split the list into two halves
Hints
- Divide and conquer: split, solve the pieces, then combine.
- Merging is only cheap because both halves are already in order.
Show the answer
- Split the list into two halves
- Sort the left half by the same method
- Sort the right half by the same method
- Merge the two sorted halves into one sorted list
- Return the merged list
Why
Splitting costs nothing, the two halves are sorted recursively, and the merge is a single linear pass because each half is ordered. The splitting depth is logarithmic and each level costs a linear merge, which is where the linearithmic total comes from.
Practise Searching and Sorting
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Searching and Sorting
- Summing a million floating-point numbers from smallest to largest is more accurate than from largest to…
- Complete the reason binary search is fast.
- Floating-point arithmetic gives 0.1 + 0.2 ≠ 0.3 on essentially every computer. Why does a well-designed…
- A sorted list holds 1,048,576 items, which is 2 to the power 20. How many halvings does binary search need to…
- A sorted list holds 64 items. Binary search halves the range at each comparison. In the worst case, how many…
- Sort each situation by the search method it calls for.