# 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

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

Advertisements

## 21 thoughts on “merge sort algorithm using recursion.”

1. sas says:

I want to merge sort the given array of numbers : 9,94,45,47,28,98,65,42,78,8,11,88,6

2. sasi says:

Solve the following inhomogeneous recurrence.
G(m)-7G(m-1)+12G(m-2)=9

3. sasi says:

Quick sort the following numbers : 9,94,45,47,28,98,65,42,78,4,11,88,6

4. sasi says:

Insertion sort the following numbers : 9,94,45,47,28,98,65,42,78,4,11,88,6

5. miamar says:

How do you implement mergesort without using recursion

1. Dheedh says:

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++];
}

6. Nate says:

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

7. varun says:

sir ur code is so large
u have used more than two arrays
so a probs is here space compexity…….

8. Sean says:

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.

9. krishnadeva says:

sir please send me the c++ code for mergeSort recursion

10. Ankit Pokhrel says:

#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;
}

11. Atieh says:

hi

tanks for your help .

have a good time , bye .

12. Manish says:

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. Dheedh says:

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 .

13. K.BENAZIR GULZAR says:

we want a quesion bank data analysis algorithm

14. kulwinder singh says:

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));
}

15. Fisha says:

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!

16. Prajwal says:

This program has a clear memory leaks

17. tensedyouth says:

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.