merge sort algorithm using recursion.


/**********************************************

-> This c++ program is to implement merge sort
   algorithm using recursion.

-> This c++ program works in the microsoft vc++
   in window xp

-> The header files used are 1) iostream.h

***********************************************/
#include<iostream.h>

class sort
{
public:
 void input();
 void mergesort(double *,int );
 void merge(double*,int,double*,int,double*,int);
 void output();
};

int n;
double *array;
void sort::input()
{
 cout<<“Enter the no of elements to be sorted ::”;
 cin>>n;
 cout<<“Now enter “<<n<<” elements ::”;
 array=new double[n];
 for(int i=0;i<n;i++)
  cin>>array[i];
}

void sort::mergesort(double *arr,int n)
{
 if(n>1)
 {
  // copy the first half to array B
  double *B;
  B=new double[n/2];
  for(int i=0;i<n/2;i++)
   B[i]=arr[i];

  // copy the second half to array C
  double *C;
  C=new double[n-n/2];
  for(int j=0;i<n;i++,j++)
   C[j]=arr[i];

  // sort them separately
  mergesort(B,n/2);
  mergesort(C,n-n/2);

  // merge the two sorted arrays
  merge(B,n/2,C,n-n/2,arr,n);
 }
}

void sort::merge(double *a,int p,double *b,int q,
     double *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)
 {
  // copy the remaing part in array 2
  while(j<q)
   c[k]=b[j],j++,k++;
 }
 else
 {
  // copy the remaing part in array 1
  while(i<p)
   c[k]=a[i],i++,k++;
 }
}

void sort::output()
{
 cout<<“The sorted list is ::\n”;
 for(int i=0;i<n;i++)
  cout<<array[i]<<‘\t’;
 cout<<endl;
}

void main()
{
 sort s;
 cout<<“*************************************”;
 cout<<“\nThis program is to sort \n”
  <<“the given numbers in increasing order \n”
  <<“using merge sort algorithm (recursion)\n”;
 cout<<“*************************************\n”;
 s.input();
 s.mergesort(array,n);
 s.output();
}

/******************************************

SAMPLE OUTPUT ::

*************************************
This program is to sort
the given numbers in increasing order
using merge sort algorithm (recursion)
*************************************
Enter the no of elements to be sorted ::5
Now enter 5 elements ::5 4 3 2 1
The sorted list is ::
1       2       3       4       5
Press any key to continue

*****************************************/

21 thoughts on “merge sort algorithm using recursion.”

    1. Recursion not my pie so🙂
      //Straightforward variant
      void merge(int lo, int m, int hi)
      {
      int i, j, k;

      // copy both halves of a to auxiliary array b
      for (i=lo; i<=hi; i++)
      b[i]=a[i];

      i=lo; j=m+1; k=lo;
      // copy back next-greatest element at each time
      while (i<=m && j<=hi)
      if (b[i]<=b[j])
      a[k++]=b[i++];
      else
      a[k++]=b[j++];
      // copy back remaining elements of first half (if any)
      while (i<=m)
      a[k++]=b[i++];
      }

  1. Vinod,
    thanks for posting your example – it looks pretty good.

    One question… the sample code allocates new memory on every call to mergesort, which I believe will result in memory utilization approaching O(n^2)

    Did you consider a version which only requires O(n) space, or does that just get too complicated for an example?

    Kind regards,
    n8

  2. Hey, thanks so much for posting this. I was looking on Wikipedia, and was trying to translate the pseudocode into C++, and was having lots of problems. Thanks a bunch for translating it.

  3. #include
    #include

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

    void mergesort(int *data,int first,int last)
    {
    int mid;
    if(first < last) //If more than one element
    {
    mid = (first + last) / 2; //Find mid
    mergesort(data,first,mid); //Sort Left Subarray
    mergesort(data,mid + 1,last); //Sort Right Subarray
    merge(data,first,mid,last); //Merge Left and Right Subarray
    }
    }

    void merge(int *data,int first,int mid,int last)
    {
    int i,j,k;
    i = first;
    j = mid + 1;
    k = 0;
    int *temp = new int[last – first + 2];
    while(i <= mid && j <= last) //While the end of Left or Right Subarray
    {
    //Compare data and save to temporary array
    if(data[i] < data[j])
    temp[k++] = data[i++];
    else
    temp[k++] = data[j++];
    }

    if(i <= mid) //If more items in Left Subarray
    for(j = i;j <= mid;j++) //Copy items to temp
    temp[k++] = data[j];
    else //more items in Right Subarray
    for(i = j;i <= last;i++)
    temp[k++] = data[i];

    k = 0;
    for(i = first;i <= last;i++) //Copy items from temporary array to original array
    data[i] = temp[k++];
    }

    int main()
    {
    int n,*arr;
    clrscr();
    cout <> n;
    arr = new int[n];
    cout << "\nEnter Elements : ";
    for(int i = 0;i > arr[i];

    mergesort(arr,0,n – 1); //Sort
    cout << endl << "\nSorted : ";
    for(int i = 0;i < n;i++)
    cout << arr[i] << ' ';

    getch();
    return 0;
    }

  4. thats g good job done by you

    but there r so many errors…………

    correct prog is as given below……

    #include
    #include

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

    void mergesort(int *data,int first,int last)
    {
    int mid;
    if(first < last) //If more than one element
    {
    mid = (first + last) / 2; //Find mid
    mergesort(data,first,mid); //Sort Left Subarray
    mergesort(data,mid + 1,last); //Sort Right Subarray
    merge(data,first,mid,last); //Merge Left and Right Subarray
    }
    }

    void merge(int *data,int first,int mid,int last)
    {
    int i,j,k;
    i = first;
    j = mid + 1;
    k = 0;
    int *temp = new int[last – first + 2];
    while(i <= mid && j <= last) //While the end of Left or Right Subarray
    {
    //Compare data and save to temporary array
    if(data[i] < data[j])
    temp[k++] = data[i++];
    else
    temp[k++] = data[j++];
    }

    if(i <= mid) //If more items in Left Subarray
    for(j = i;j <= mid;j++) //Copy items to temp
    temp[k++] = data[j];
    else //more items in Right Subarray
    for(i = j;i <= last;i++)
    temp[k++] = data[i];

    k = 0;
    for(i = first;i <= last;i++) //Copy items from temporary array to original array
    data[i] = temp[k++];
    }

    int main()
    {
    int n,*arr;
    clrscr();
    cout<<"*************** Welcome to Merge Sort **************";
    cout<>n;
    arr = new int[n];
    cout << "\nEnter Elements : ";
    for(int i = 0;i>arr[i];

    mergesort(arr,0,n+1); //Sort
    cout << endl << "\nSorted : ";
    for(i = 0;i < n;i++)
    cout << arr[i] << ' ';
    cout<<"\nyou have done a good job";
    getch();
    return 0;
    }

    feel good………….feel live……….
    Radio Manav Rachna 107.8……………..(:

    1. How does recursion do the sorting of your left array and then right array , I have spent hrs on understanding the 2 recursive calls and all i end up is only confusion . Could u plz explain its idea by an example b/c it boils down to containing single element .

  5. Sir, i need ur help….

    find send me algorithm of following program using recursion

    #include
    int fact(int);
    int main(){
    int num,f;
    printf(“\nEnter a number: “);
    scanf(“%d”,&num);
    f=fact(num);
    printf(“\nFactorial of %d is: %d”,num,f);
    return 0;
    }

    int fact(int n){
    if(n==1)
    return 1;
    else
    return(n*fact(n-1));
    }

  6. i am really greatful about the leason. The code is very clear ,so intererting, easy to understand and i really like so much!!! Thanks so much once again!

  7. Your program is SO less efficient than many other solutions.😐 Your logic is correct but the way you have implemented the logic is not efficient.
    Try referring to the book by Cormen.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s