Merge sort is one of the most beautiful and simplest algorithms. Its very short and at the same time very powerful because of its O(n * log n) speed.
Its very hard to wrap your mind around it at first because it uses recursion. But if you give me the next 3 minutes you will completely understand how it works, and why it works like it does.
Here is how simple merge sort looks in pseudo code
If one item Return Else Merge-sort left half Merge-sort right half Merge halves
That’s it. If you look at the else statement you can see that the marge sort function calls itself, in a pattern programmers call “recursion”.
Lets follow it line by line with a simple 3 items array [ 2, 3, 1 ]. Merge sort works on every array size applying this basic principles.
And flatten the instructions the the computer gets understanding one simple principle.
Only one instruction goes on at a time. And the instructions for the rest of the code live on something called “the stack” in memory. And when you call a new function it goes on the top of the stack and therefor executes first
You can think of it this way as computer interprets it. In flattened code.
If one item [ 2, 1 , 3 ] Else Merge sort left half [2, 1 ] ------- To stack -- Merge-sort right half  -- Merge halves -------- If one item [ 2 , 1 ] Else Merge sort left half [ 2 ] ----- To stack -- Merge-sort right half  -- Merge halves -------- Is one item [2 ] Return to line 9. Is one item [ 1 ] Return to to line 11. Merge halves  &  = [1 , 2] Is one item  ( back from line 5) Return to line 5. Merge Halves [1, 2] &  = [1, 2, 3]
Want computer science topics sent to your inbox weekly?