Merge sort Algorithm and Program in C C++

The merge sort is a sorting algorithm that uses the divide and conquer strategy . in this method ,division is dynamically carried out .
Merge sort on an input array with n elements consists of three steps.
1) Divide : Partition array into two sublists s1 and s2 with n/2 elements each .
2) Conquer : Recursively sort s1 and s2 .
3) Combine : Merge s1 and s2 into a unique sorted group .
               The merge sort divides the given list into two sublists recursively until each sublist contains only one element .Then we apply the same merging process recursively as explained above to obtain the sorted list . If the single file or list contains N elements then it is divided into two sublists containing N/2 elements which are further divided into sublists containing N/4 elements and so on.
Also check : Program for Insertion sort 

Algorithm for Merge sort :

Mergingsortedsubarrays(a , lb , lr , rb , rr)
        Here a is a linear array , variables lb ,lr represents beginning and ending indices of the left sub array and variables rb ,rr represents beginning and ending indices of the right sub array .The algorithm merges these two sub arrays .It uses local variables na ,nb as counters to keep track of the elements of left and right sub array respectively which are candidates to go to temporary array c and nc as counter to keep track of the position in c , where the incoming elements will be stored .

Begin
    set na=lb, nb=rb and nc=lb
    while((na<=lr) and (nb<=rr)) do
        if(a[na]<b[nb]) then
            Set c[nc]=a[na]
            set na=na+1
        else
            set c[nc]=a[nb];
            set nb=nb+1;
        endif
            setnc=nc+1
    endwhile
    if(na>lr) then
        while(nb<=rr)then
        set c[nc]=b[nb];
        set nb=nb+1;
        set nc=nc+1;
        endwhile
    else
        while(na<=lr) then
            set c[nc]=b[na];
            set na=na+1;
            set nc=nc+1;
        endwhile
    endif
    for k=lb to rr by 1 do
        set a[k]=c[k]
    endfor
End

After the procedure for merging to halves is defined the various steps required for mergesort are summarized in the following algorithm ,

Algorithm : Mergesort(a , beg , end)

      Here a is a linear array with lower bound beg and upper bound end .The algorithm sorts the array using merge sort method .It uses variable mid to represent the index of the element at which array will be divided into two halves .

Begin
    if(beg<end) then
        set mid = (beg+end)/2;
        call mergesort(a,beg,mid);
        call mergesort(a,mid+1,end);
        call mergingsortedsubarray(a,beg,mid,mid+1,end)
    endif
End

The recursive procedure mergesortmethod() will be called from the calling function by the call statement as a.mergesortmethod(0 , n-1) , where a is an array of size n.

Program to Implement Merge Sort :

#include<iostream>
using namespace std;
template<class T>
class array
{
 T *a,*c;
 int size;
 public :
 array(int n)
 {
  size=n;
  a = new T[n];
  c = new T[n];
 }
 ~array()
 {
  delete a;
  delete c;
 }
 void inputarray();
 void outputarray();
 void mergingsortedsubarrays(int ,int ,int ,int );
 void mergesortrecursive(int ,int );
 void mergesort();
}
//Function to get elements into array
template<class T>
void array<T>::inputarray()
{
 int i;
 cout<<"\nEnter"size<<"elements of arrayn\n";
 for(i=0;i<size;i++)
 {
  cin>>a[i];
 }
}
//Function to  display array elements
template<class T>
void array<T>::outputarray()
{
 int i;
 for(i=0;i<size;i++)
 {
  cout<<a[i]<<"t";
 }
 cout<<endl;
}
//Function to merge two sorted sub arrays
template<class T>
void array<T>::mergingsortedsubarrays(int lb,int lr,int rb,int rr)
{
 int na,nb,nc,k;
 na=lb;
 nb=rb;
 nc=lb;
 while((na<=lr)&&(nb<=rr))
 {
  if(a[na]<a[nb])
   c[nc]=a[na++];
  else
   c[nc]=a[nb++];
 }
 if(na>lr)
 {
  while(nb<=rr)
  c[nc++]=a[nb++];
 }
 else
 {
  while(na<=lr)
   c[nc++]=a[na++];
 }
 for(k=lb;k<=rr;k++)
 a[k]=c[k];
}
//Recursive function of mergesort
template<class T>
void array<T>::mergesortrecursive(int beg,int end)
{
 int mid;
 if(beg<end)
 {
  mid=(beg+end)/2;
  mergesortrecursive(beg ,mid);
  mergesortrecursive(mid+1 ,end);
  mergingsortedsubarrays(beg , mid,mid+1,end);
 }
}
//Main Function
void main()
{
 int s;
 cout<<"Enter size of array";
 cin>>a;
 array<int> a(s);
 a.inputarray();
 cout<<"\n Input array is:";
 a.outputarray();
 a.mergesortrecursive(0,s-1);
 cout<<"\nsorted array is:";
 a.outputarray();
}

Time complexity of Merge sort( Efficiency) :

The major work is done in the merge procedure ,which is an O9n) operation ,The merge procedure is called from merge-sort procedure after the array is divided into two halves and each half has been sorted .In each of the recursive calls one for left half and one for right half , the array is divided into two halves , thus dividing the array into four segments .At each level , the number of segments doubles .Therefore the total divisions are logn 
       The only disadvantage of merge sort is that it uses an extra temporary array ,of the same size as that of input array ,to merge the two halves .The elements of the temporary array are copied back to the original array before the next merging .

Final words!

If I had missed anything please let me know through comments . Also share your logic through comments .