Home » C++ programming language

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.

#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

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.