Home » C++ programming language

Merge Sort in C++ with Example



Learn: Merge Sort in C++ with Example, Algorithm. Merge sort is the sorting technique of Data Structure, here we will learn Merge sort implementation using C++.
Submitted by Shubham Singh Rajawat, on June 09, 2017

Merge sort follows the approach of Divide and Conquer.

Divide means breaking a problem into many small sub problems.

Conquer means solving those small sub problems recursively and then recombine them to create a solution of the original problem.

The method MergeSort() breaks the array into equal parts until every element get separated and then the method Merge() recombines them while sorting them every time it joins two arrays it joins them in a sorted way so that we get a final sorted array.

Program for Merge Sort in C++

#include<iostream>

using namespace std;

void Merge(int A[],int p, int q,int r)     /*It merges two arrays */
{

	int n1=q-p+1,i,j,k;       /*n1 is the size of L[]*/

	int n2=r-q;               /*n2 is the sixe of R[]*/

	int L[n1],R[n2];

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

	{
		L[i]=A[p+i];
	}

	for(j=0;j<n2;j++)
	{
		R[j]=A[q+j+1];
	}

	i=0,j=0;

	for(k=p;i<n1&&j<n2;k++)
	{
		if(L[i]<R[j])
		{
			A[k]=L[i++];
		}
		else
		{
			A[k]=R[j++];
		}
	}

	while(i<n1)             /*If L[] has more elements than R[] then it will put all the reamining elements of L[] into A[]*/
	{
		A[k++]=L[i++];
	}
	
	while(j<n2)             /*If R[] has more elements than L[] then it will put all the reamining elements of R[] into A[]*/  
	{
		A[k++]=R[j++];
	}
}

void MergeSort(int A[],int p,int r)    /*It will will divide the array and sort them while merging them*/
{
	int q;                                

	if(p<r)
	{
		q=(p+r)/2;                      /*q is the middle element to divide the array*/ 
		MergeSort(A,p,q);
		MergeSort(A,q+1,r);
		Merge(A,p,q,r);
	}

}


int main()
{

	int A_Size;                          /*A_Size size of A[]*/    

	cout<<"Enter number of elements :";

	cin>>A_Size;

	int A[A_Size];
	
	cout<<"Enter the array elements :";

	for(int i=0;i<A_Size;i++)
	{
		cin>>A[i];
	}

	MergeSort(A,0,A_Size-1);

	for(int i=0;i<A_Size;i++)
	{
		cout<<A[i]<<" ";
	}

	cout<<endl;
}

Output

First Run:
Enter the no of elements: 7
Enter the array elements: 100 99 768 986 67 13 9
9 13 67 99 100 768 986

Second Run:
Enter the no of elements: 10
Enter the array elements: 55 32 1 19 29 40 100 89 77 13
1 13 19 29 32 40 55 77 89 100





Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.



Comments and Discussions


We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.