C or C++ Program for Merge Sort

This article describes about the program to perform about Merge Sort in C/C++. Let us discuss about Merge sort.

Merge Sort
Merge Sort is a sorting technique based comparison. At first it divides the list into the smallest unit (1 element). Then compare each element with the adjacent list to sort and merge the two adjacent lists. At last all the elements are sorted and merged. It is Stable and takes O (n log n) times.

Merge Sort Program

#include
#include
class node
{
    int a[100];
    int p,q,r,n;
public:
    void get_data();
    void merge(int,int,int);
    void merge_sort(int,int);
    void show_data();
}tap;

void node::get_data()
{
  cout<<"This is a Merge sort program\n\n\n";
  cout<<"How many number you want to enter :";   cin>>n;
  cout<<"Enter the values :\n";
    for(int i=1;i<=n;i++) 	cin>>a[i];
	r=n;
    tap.merge_sort(1,r);
    tap.show_data();
}

void node::merge(int p, int q,int r)
{
    int n1=q-p+1;
    int n2=r-q;
    int L[100];
    int R[100];
    for(int i=1;i<=n1;i++)
        L[i]=a[p+i-1];
    for(int j=1;j<=n2;j++)
        R[j]=a[q+j];
        L[n1+1]=999;
        R[n2+1]=999;
        i=1;
        j=1;
    for(int k=p;k<=r;k++)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
    }
}

void node::merge_sort(int p,int r)
{
if(p<r)
    {
	    int q=(p+r)/2;
	    merge_sort(p,q);
	    merge_sort(q+1,r);
	    merge(p,q,r);
    }
}

void node::show_data()
{
    cout<<"After sorting......\n\n";
    for(int i=1;i<=n;i++)
    cout<<"\t"<<a[i];
}

void main()
{
    clrscr();
    tap.get_data();
    getch();
}