How to merge two sorted arrays? Merging Sort Algorithm, Explanations with Animated Presentation, The Program



Merging Sort: 

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.






Download the Above Presentation (1.97 MB)



ContentMiddleAd


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.

/*
Data Structure Lab Test
Date 16/04/2011
Programmed by Tanmay Chakrabarty
CSE.

Compiled successfully with Turbo C++ 4.5
*/

#include<iostream.h>

int main()
{
int first_array_size, second_array_size,i,j,k, merged_array_size;

/*
i will be used for the first array.
j will be used for the second array.
k will be used for the merged array.
*/

cout<<"PLEASE READ: No kind of input exceptions has been handled.\n";
cout<<"Don't Play with Inputs.\n";
cout<<"__________________________________________________________\n\n";

cout<<"Please enter the number of elements of the first list : ";
cin>>first_array_size;

int *first_array = new int [first_array_size];

cout<<"\nPlease enter the elements of first list in ascending order\n\n\t";
for(i=0;i<first_array_size;i++)
 cin>>first_array[i];

cout<<"\nPlease enter the number of elements of the second list : ";
cin>>second_array_size;

int *second_array = new int [second_array_size];

cout<<"\nPlease enter the elements of second list in ascending order\n\n\t";
for(j=0;j<second_array_size;j++)
 cin>>second_array[j];
        
merged_array_size=first_array_size + second_array_size;

int *merged_array=new int [merged_array_size];

j=i=k=0;

//Loop continues till we are inside of both of the arrays
while(i<first_array_size && j<second_array_size)
 {
 if(first_array[i] < second_array[j])   //Finding the lowest
  {
  merged_array[k]=first_array[i];     //Putting it in the merged array
  i++; //As value from first array has been taken, increasing i
  k++;  //increasing k for the next space of the merged array
  }
 else
  {
  merged_array[k]=second_array[j];
  j++;
  k++;
  }
 }

if(i==first_array_size) //it means, all values from first array has been taken
 {
 for(j=j;j<second_array_size;j++) //Thus taking rest of the values of the second array
  {
  merged_array[k]=second_array[j];
  k++;
  }
 }
else if(j==second_array_size) //it means, all values from second array has been taken
 {
 for(i=i;i<first_array_size;i++)  //Thus taking rest of the values of the first array
  {
  merged_array[k]=first_array[i];
  k++;
  }
 }
else  //it means all the values from the two arrays has been taken and nothing to do.
 {
 }
cout<<"\n\nThe Merged array is as follows:\n\n";
for(i=0;i<merged_array_size;i++)  //Now we can print the merged array
 {
    if(i != (merged_array_size - 1))
        cout<<merged_array[i]<<" , ";
    else
        cout<<merged_array[i]<<"\n\n";
    }

system("pause");
return 0;
}

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,


                     

Download the Above Program (150 KB)



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.

Recommended Recommends

Comments

Contact Us

Loading...