In this tutorial, you will learn how a merge sort works. Merge sort is a kind of divide and conquer sorting algorithm. Here, we have implemented merge sort technique in C++.

Example for merge sort algorithm

Let us take the elements of array as A = 1,5,8,3,4,7,2,6. Take a look at the picture

Here, we divide the arrays into sub problems. At the half-way, we divide the array, until we reach the base. After that we combine the arrays according to the value of the element and merge them to get the final array. Merge sort array is implemented using recursion technique, which you can find here.

Brief of code

**merge_sort**function- We call the
**merge_sort**on the array a. Left and Right are the base index. - At starting, Left is 0 and Right is size-1.
- The
**merge_sort**will return, if only one element is present while calling**merge_sort** - And then, the counter moves to
**merge**function. **merge**function- In merge function, we combine the elements of the arrays.
- Two arrays are created,
**leftArr**and**rightArr**. - The elements are inserted into these arrays.
**leftArr**contains elements from 0 to mid and**rightArr**contains elements from mid+1 to size. - Then we compare elements of these arrays and insert into the main array
**a[ ]**. - This happens till one of the array empties, then we fill the array a[ ], with the remaining elements.
- Code is implemented below.

The code is implemented in C++ here

```
#include<iostream>
using namespace std;
void print(int a[],int size){
cout<<"The elements are ";
for(int i=0;i<size;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
void merge(int a[],int left,int mid,int right){
int nl = mid-left+1;
int nr = right-mid;
int leftArr[nl];
int rightArr[nr];
for(int i=0;i<nl;i++){
leftArr[i] = a[left+i];
}
for(int j=0;j<nr;j++){
rightArr[j] = a[mid+j+1];
}
int i=0,j=0,k=left;
while(i<nl && j<nr){
if(leftArr[i]<rightArr[j]){
a[k] = leftArr[i];
i++;
}
else{
a[k] = rightArr[j];
j++;
}
k++;
}
while(i<nl){
a[k] = leftArr[i];
i++;
k++;
}
while(j<nr){
a[k] = rightArr[j];
j++;
k++;
}
}
void merge_sort(int a[],int left,int right){
//left,mid and right are index numbers
int size = right - left + 1;
if(size<2)return;
int mid = left + (right-left)/2;
merge_sort(a,left,mid);
merge_sort(a,mid+1,right);
merge(a,left,mid,right);
}
int main(){
int a[]={1,5,8,3,4,7,2,6};
int size = sizeof(a)/sizeof(int);
print(a,size);
merge_sort(a,0,size-1);
print(a,size);
return 0;
}
```

## One Reply to “Merge Sort in C++”