MergeSort.cpp

/******************************
  	MergeSort.cpp
    Auther:Syed Zain Ul hasan
  *****************************/


#include <iostream>
using namespace std;


 //function for merging two sorted array
void Merge(int *L,int  *R,int* A,int nL,int nR)
{
	int i=0,j=0,k=0;

	while(i<nL && j<nR)
	{
		if(L[i]<=R[j]){
			A[k]=L[i];
			i++;
		}
		else{
			A[k]=R[j];
			j++;
		}
		k++;
	}

	//remaing values
	while(i<nL){
		A[k]=L[i];
		i++;k++;

	}
	while(j<nR){
		A[k]=R[j];
		j++;k++;
	}

}
//function for merge sort
void merge_sort(int* A,int n)
{
	if(n<2)
		return;
	else{
		int mid=n/2;

		//make left array
		int *left=new int [mid];
		int *right=new int[n-mid];

		//fill these arrays
		for(int i=0;i<mid;i++)
			left[i]=A[i];
		for(int i=mid;i<n;i++)
			right[i-mid]=A[i];

		int nL=mid;//number of elements in Left array
		int nR=n-mid; //number of elements in right array

		merge_sort(left,nL);
		merge_sort(right,nR);

		Merge(left,right,A,nL,nR);
	}
}

int main() {

	int arr[7]={1,4,3,5,14,12,0};

	merge_sort(arr,7);//sorting

	//now print array
	for(int i=0;i<7;i++)
		cout<<arr[i]<<" ";


	return 0;
}