Merge Sort is a sorting technique based on Divide and Conquer principle, in merge sort we first divide the array into two equal halves and merge them together into sorted manner. With worst case time complexity of O(n log n), it is one of the most respected algorithms.
Explanation :
Basically what we do in merge sort is pretty straight forward, we first divide the array into equal halves until we reach a point where no more division can take place and then sorting takes place, once sorting is done completely, we merge the sorted array and hence we obtain our sorted array.
Example:
Let's take an unsorted array to start with our example.
4 2 6 1 7 5 3 8
we now divide the array into two equal parts , i.e of three parts, so after this step we've our array as..
4 2 6 1 - 7 5 3 8
(Where the ' - ' signifies the two divided parts.)
we still can divide our array into two parts, so..
4 2 - 6 1 - 7 5 - 3 8
Again we divide to obtain..
4 - 2 - 6 - 1 - 7 - 5 - 3 - 8
Now we observe that no further division of array can take place, so our next step will be to combine them in the exact same order in which they were broken down. Here we first compare the elements in each list and then combine them into another list in sorted manner. We observe that 4 and 2 are not sorted order so we swap there positions, same goes for 6 & 1, so we swap there positions too, also for 7 & 5, but 3 and 8 are in correct position, so we leave them as it is. So we've our array as follows after this step..
2 4 - 1 6 - 5 7 - 3 8
Now after this step we've to check order for 2,4,1 and 6 we see correct order is 1,2,4 and 6 similarly for 5,7,3 and 8 correct order is 3,5,7 and 8. so after this step we've our array as follows....
1 2 4 6 - 3 5 7 8
and you can guess how the final step will turn up so we get our sorted array..
1 2 3 4 5 6 7 8
Well, this the mechanism for Merge Sort , next we'll be looking at its coding part in C so that we can implement the concept we just understood.
Merge Sort C Code :
Output of the above program is :
if you find any problem in the above code, then kindly add a comment in the comment section.
