Understanding Merge Sort

In order to understand how merge sort works, we first need to talk about merging two sorted lists. So, if we are given two sorted lists:

 4  15  16  50                    8  23  42  108

and we have to sort them into one list we can take the advantage of the fact that they are sorted lists. The first element of the new sorted list must contain the smallest element. Now, as we know these lists are already sorted that means we just need to compare the first element of both the lists and whichever is small get inserted into the new list. That means, we compare 4 and 8 and as 4 is small it gets into the new list. Then we compare 15 and 8, the first element of first and second list and as 8 is small it gets into the new list. We continue with the same procedure until every element from 1st and 2nd list gets into the new list. That's exactly how merge sort works.

There are two big steps in the process of merge sort:

1) Continuously split the number of elements into half until we have a bunch of lists which have only       one element in them(single elements are always sorted i.e. we have a bunch of sorted lists).

2) Repeatedly merge pairs of lists using the merge algorithm we discussed above.

Let's take an example. Suppose we have to sort the given list:

     108  15  50  4  8  42  23  16

Let's split it into half

      108  15  50  4   |   8  42  23  16

Now, we have two lists, we repeat until we have every element seperated into individual list as:

     108  |  15  |  50  |  4  |  8  |  42  |  23  |  16

Now, we merge first two lists i.e. 108 and 15 using the above method that is we compare and place the small one in the new list. So, the list becomes: 

     15  108  |  50  |  4  |  8  |  42  |  23  |  16

Again, we merge 15 108 and 50, new list become:

     15  50  108  |  4  |  8  |  42  |  23  |  16

Repeatedly doing this we get:

     4  8  15  16  23  42  50  108

this is a sorted list!

Though, merge sort generally works better than bubble, insertion and selection sort but there is also a drawback, in order to merge two lists it needs extra space.

That's the basics of merge sort. Go ahead and try to implement it and in case you need some help check out the references.

Contributor's Info