Dmitry Kalashnikov

Mergesort: Split data in two halfs, mergesort each half, then merge these already sorted halfs back into a single piece.

Mergesort and merge are two separate functions. Think of merge as a helper function that does most of the work. Its much easier to explain with a very high-level pseudo code:

Function Mergesort (A):

B = First half of A
C = Second half of A
Mergesort(B)
Mergesort(C)

/* Important: B and C area already sorted at this point. We just need to merge them into A */
Merge(B, C, A)

Function Merge(B, C, A):
/* Merges 2 already sorted arrays (B and C) into one sorted array (A) */
While B and C still have elements:
keep taking the smallest element from B or C, and appending it to A

Analysis: It’s a two step process:

1. We constantly keep splitting data into two (until we can’t split it any more)
2. Then we keep merging splited pieces into a single piece.

it “Big O” is: O(n lg n) because it takes lg n “levels” in the tree to break it down, then n-times to merge them. See my refresher on logarithms if you don’t understand what lg n means.

So, thats the basic idea. Its pretty simple really. I’ll update this post and add some actual code in various languages later on. Maybe using C# and ruby.