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 ]
Is one item [ 1 ]

Merge halves  &  = [1 , 2]

Is one item  ( back from line 5)