Merge Sort in C++

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

merge sorting
merge sorting

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;
}
output of the above program. merge sort
output of the above program. merge sort

Leave a Reply