Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The mergeSortedArrays() function is used for merging two halves.

MergeSort.cpp

#include <iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; 

void mergeSortedArrays(int* arrData,int *arrLeft,int leftCount,int* arrRight, int rightCount){
     int i =0,j=0,k=0;
     
     while(i < leftCount && j < rightCount){
           if(arrLeft[i] < arrRight[j]){
           	arrData[k++] = arrLeft[i++];
		   }else{
		   	arrData[k++] = arrRight[j++];
		   }	
	 }
	 
	 while(i < leftCount){
		arrData[k++] = arrLeft[i++];
	 }
		   
	 while(j < rightCount){
		arrData[k++] = arrRight[j++];
	}
}

void mergeSort(int* arrData, int size){
	if(size < 2){
		return;
	}
	
	int mid = size/2;
	int i = 0;
	int* arrLeft = (int*)malloc(mid*sizeof(int));
	int* arrRight = (int*)malloc((size-mid)*sizeof(int));
	
	for( i = 0; i< mid;i++){
		arrLeft[i] = arrData[i];
	}
	
	for( i = mid; i < size;i++){
		arrRight[i-mid] = arrData[i]; 
	}
	
	mergeSort(arrLeft,mid);
	mergeSort(arrRight,size-mid);
	mergeSortedArrays(arrData,arrLeft,mid,arrRight,size-mid);
	free(arrLeft);
	free(arrRight);
}

int main(){
	
	int arrData[] = {6,2,3,1,9,10,15,13,12,17};
	int sizeOfData = sizeof(arrData)/sizeof(arrData[0]);
	mergeSort(arrData,sizeOfData);
	for(int i = 0;i < sizeOfData; i++){
		cout<<arrData[i]<<" ";
	}
	
	return 0;
}