Merging sort requires two previously sorted array which will be merged into one single array which will be a sorted array. If the source arrays are not sorted then the algorithm won’t work. If you need to sort two unsorted arrays then you can place one array after another then operate the new array with any sorting algorithm to sort it. Another important thing is that, the source arrays will have to be there in sorted in the same order, either ascending or descending.
Bored with text? Watch the video.
In this algorithm, I assume that you have two source arrays which are sorted in ascending order and you want the resulted merged array in ascending too. Well if your requirements are not these then you will have to change some of the places of the algorithm to suit your needs.
The Merging Sort Algorithm:
Well, I am not going to rewrite the algorithm as I am using the algorithm from the book “Data Structures” by Seymour Lipschutz Tata McGraw-Hill Edition 2002, Sixth Reprint 2004. Following is the scanned copy of the algorithm.
Well, I will not discuss this algorithm rather I am providing you an animated presentation of the whole process. I am 100% sure that the presentation will help you understand the whole process and work-through in a much better way than writing a thousands of words here explaining the process. Before downloading the presentation you can see what you are downloading.
The Program for Merging Sort:
I wrote this program while I was giving the lab test of the course data structure in my campus. There are enough comments for you to understand the code. In the above presentation I explained the whole process with debugging and displaying information, so I think you have already understood the process. However, you can still take the help of the comments.
Well, so that’s it. Here I don’t have any code snippet, so the code may seem to a little distorted. However, there is a download link for the code and the application, make use of that, if you want. Following is the output,
Well, I am sorry if this post have not satisfied you, but this is what I do. I don’t get much time to post here though I always like to share things, getting helps from others. However, if you have any problem, leave that here, I will reply as soon as possible.
I have written an algorithm for the MERGE sort, my next post will be that. But it is seeming to me that it is much harder for me to explain the algorithm I wrote than writing it. Okay, see you in the next post.