merge sort

As is indicated by the name, Mergesort works by merging two sorted arrays into one large array. How can we get sorted arrays out of an unsorted array? By repeatedly cutting the array in half, and thus we get two half-arrays, then four quarter-arrays… and finally, we get n arrays of only one element in it, where n is the number of elements in the original array.

See the trick here: we now have n sorted arrays, for every array has only one element in it!

Now we work the process backwards by merge every pair of arrays into a “mother” array. In other words, if we get Array B and Array C but cutting Array A in half, we’ll merge Array B and Array C into a new Array A’. Unlike the unsorted Array A, our new Array A’ will be sorted. We work all the way back to our original array, we’ll get a sorted version of the original array, as we are asked to.

So, our problem becomes “how to merge two small sorted sub-arrays into a large sorted array?” Here is how it works:

1. Compare the first elements of the two sub-array. The smaller of the two is the smallest among the two sub-arrays. By way of illustration, let’s say the first element of sub-array B is the smallest, so we’ll set it to be first element of our large array A.
2. Since the first element of sub-array B has done its work, i.e. finding its proper place in array A, we can move on to the second element of B, can compare it with the first element of C (which hasn’t find its place). Again, we move the smaller to Array A.
3. Repeat Step 2, until either sub-array B or C runs out of elements. Let’s say B is depleted, which means the remaining element of C is larger than any elements of B, so we can just move them, in their order, to the end of Array C. And we are done!