C++ program to implement Merge Sort

#include<iostream>
using namespace std;
 void mergesort(int *,int );

 void merge(int*,int,int*,int,int*,int);

 

 int main()

 {  int *arr,n;

    cout<<"Enter the no of elements ";

    cin>>n;

    arr=new int[n];

    for(int i=0;i<n;i++)

    cin>>arr[i];

    mergesort(arr,n);

    for(i=0;i<n;i++)

    cout<<arr[i]<<" ";

    return 0;

}

 

void mergesort(int *arr,int n)

{

      if(n>1)

      {

               int *b;

               b=new int[n/2];

               for(int i=0;i<n/2;i++)

               b[i]=arr[i];

 

               int *c;

               c=new int[n-n/2];

               for(int j=0;i<n;i++,j++)

               c[j]=arr[i];

 

               mergesort(b,n/2);

               mergesort(c,n-n/2);

 

               merge(b,n/2,c,n-n/2,arr,n);

      }

}

 

 

void merge(int *a,int p,int *b,int q,int *c,int n)

{

      int i,j,k;

      i=j=k=0;

      while(i<p && j<q)

      {

               if(a[i]<=b[j])

                          c[k]=a[i],i++;

               else

                          c[k]=b[j],j++;

               k++;

      }

      if(i==p)

      {

               while(j<q)

                c[k]=b[j],j++,k++;

      }

      else

      {

               while(i<p)

                 c[k]=a[i],i++,k++;

      }

}

Input

Enter how many elements : 6

23  43  11  12  67  38

Output

11  12  23  38  43  67

Leave a comment

Your email address will not be published. Required fields are marked *