Merge Sort:

Steps:

Code:
http://www.code2learn.com/2011/07/merge-sort-using-java.html



eg:
{2, 4, 1, 6, 8, 5, 3, 7}

Divide the array into half recursively, till at the end you have only one element in the array
so divisions at each step are:
1. {2, 4, 1, 6} {8, 5, 3, 7}
{2, 4} {1, 6} {8, 5} {3, 7}
{2} {4} {1} {6}  {8} {5} {3} {7}


2. Now merge two arrays: {2}, {4} into a single array in sorted order ==> {2,4}
   similarly merge two arrays: {1}, {6} into a single array in sorted order {1,6}
 
   Now merge these two arrays in sorted order. ==> {1, 2, 4, 6}
 
   Similarly you get another array: {3, 5, 7, 8}
 
   At the last step array is sorted as: {1, 2, 3, 4, 5, 6, 7, 8}
 
3. How two unsorted arrays are merged in sorted fashion.
Consider the first element of first array and first element of second array
compare these two and place the lesser number in the target sorted array
Lets say first < second.
Now increase the index of first position by 1 and compare this with right, ie. first+1 < second?

Here we are placing all smaller elements one by one in sorted array.
For eg:
left: {1, 2, 4, 6}
right: {3, 5, 7, 8}
Sorted Array:
{0, 0, 0, 0, 0, 0, 0, 0} left: {1, 2, 4, 6}, right: {3, 5, 7, 8}
{1, 0, 0, 0, 0, 0, 0, 0} left: {2, 4, 6}, right: {3, 5, 7, 8}
{1, 2, 0, 0, 0, 0, 0, 0} left: {4, 6}, right: {3, 5, 7, 8}
{1, 2, 3, 0, 0, 0, 0, 0} left: {4, 6}, right: {5, 7, 8}
{1, 2, 3, 4, 0, 0, 0, 0} left: {6}, right: {5, 7, 8}
{1, 2, 3, 4, 5, 0, 0, 0} left: {6}, right: {7, 8}
{1, 2, 3, 4, 5, 6, 0, 0} left: {}, right: {7, 8}
{1, 2, 3, 4, 5, 6, 7, 0} left: {}, right: {8}
{1, 2, 3, 4, 5, 6, 7, 8} left: {}, right: {}

Complexity: