C C++ Java Data Structure Python JavaScript CSS Ajax PL/SQL PHP Puzzles C programs C++ programs Java programs

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








COMMENTS