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 [3]
    -- Merge halves
    --------
If one item [ 2 , 1 ]
Else
    Merge sort left half [ 2 ]
    ----- To stack
    -- Merge-sort right half [1]
    -- Merge halves
    --------
Is one item [2 ]
    Return to line 9.
Is one item [ 1 ]
    Return to to line 11.
    
Merge halves [1] & [2] = [1 , 2]

Is one item [3] ( back from line 5)
    Return to line 5.
    
Merge Halves [1, 2] & [3] = [1, 2, 3]

Array sorted!

Alternative graph look

Want computer science topics sent to your inbox weekly?

Subscribe

Get CrunchSkills in your inbox weekly. Stay sharp for your next technical interview.