Practice question · Put in order
Order how merge sort applies divide-and-conquer to a list.
- Merge the two sorted halves into one
- Recursively sort the right half
- Split the list into two halves
- Recursively sort the left half
Hints
- Divide before you conquer, and conquer before you combine.
- Merging is the combine step and comes last.
Show the answer
- Split the list into two halves
- Recursively sort the left half
- Recursively sort the right half
- Merge the two sorted halves into one
Why
Split, sort each half, then merge. The merge is cheap (linear), which is exactly the condition that makes divide-and-conquer pay off here.
Practise Divide-and-Conquer Reasoning
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.