It took me a while to piece it together. It's not as natural as a normal fibonacci or tree operations.
Answer1: Drawing and figuring out the order.
Robert Harvey's answer really helped me get on track.
First tip. Try paper. How you outline things on paper are critical for understanding it.
My answer is based off of the following PDF from University of Purdue. Once you see that diagram, you then need to understand the order of operations. Otherwise you won't be able to put it together.
Notice the green numbers. That's exactly the order that a merge sort recursively computes its result.
It's recursively splitting til it gets to a leaf (array with a count of 1) and creeping back up then. You basically first try to get to the bottom left leaf and every other leaf from the left and come back up, til you get to the right side. The right side (of the original array) doesn't start until the entirety of the left side is done. Then all the right side goes on, until both sides have a sorted array and then you sort them against one another as the last step.
Steps 5,10, 11 are the only steps that are backwards.
Make sure you see that pdf. It has a lot of single step slides. Make it much easier to comprehend.
Answer2: Think of this answer more as a series of comments:
I came to this question and some other links to figure it out. This is how I answer it:
Do you know how to merge two (sorted) arrays?
[2, 18, 30]
& [5, 9, 22]
.
You just keep comparing the first item and putting into a new sorted array
Do you know how to split an array into two sections?
Just split from the middle
What needs to be done on each split?
Need to perform mergeSort, otherwise your two arrays won't be sorted. This is the heart of it, but also where you don't need to care of its details, until you get to implementation details.
We need a base i.e. one that shouldn't call anything else recursively. Do you know how you get to that?
We just get to it by splitting enough till there's only a single item in the array. Where it can't be split.
What's also tricky is: With the exception of where the array's length is less than 2, The the base case while it returns, is never meant to be the answer. It's just an intermediate array for comparison.
This is similar to what Robert Harvey said in his answer:
Visually, you can think of it as a tree-like structure, with the root at the top and progressively smaller branches extending downward.
i.e. you need the answers of the leafs to be able to get the answer of the root.
Do you know how to test the logic of it as a whole?
Yeah, just I'll just use a [3,2]
array. Split it in two. [3]
& [2]
and then start comparing from the first item in each array and place them in a sorted array.
Sample Swift code:
func mergeSort(array: [Int]) -> [Int] {
// 1. base case
guard array.count > 1 else {
return array
}
let leftArray = Array(array[0..<array.count / 2])
let rightArray = Array(array[array.count / 2..<array.count])
// 2. recursive call
return merge(left: mergeSort(array: leftArray), right: mergeSort(array: rightArray))
}
// 3. work done in each iteration
func merge(left: [Int], right: [Int]) -> [Int] {
var left = left
var right = right
var sorted: [Int] = []
while left.count > 0 && right.count > 0 {
if right.first! >= left.first! {
sorted.append(left.removeFirst())
} else {
sorted.append(right.removeFirst())
}
}
sorted += left + right
return sorted
}