Merge Sort in C++

Merge Sort

The detailed algorithm and explanation is shared here: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more

Here is the algorithm in short:

Divide the given array into two.

pass each into mergesort

merge these two arrays into one.

return this new array.

Here is the code for mergesort function in c++:

void mergeSort(int* arr, int l ,int r){
	if(l<r){
	int m= (r+l)/2;
	mergeSort(arr, l, m);
	mergeSort(arr, m+1, r);
	merge(arr, l, m, r);
	}
	}

The algorithm for merge function is:

• create two new arrays of lengths equal to these subarrays. Copy the contents into these.
• start iterating in two arrays, check for which element is shorter among the two and push the shorter into the original array.

Here is the code for merge in c++:

void merge(int* arr, int l, int m, int r){
	int n1 = m-l+1;
	int n2 = r-m;
	int left[n1];
	int right[n2];
	for (size_t i = 0; i < n1; i++) {
	left[i] = arr[l+i];
	}
	for (size_t j = 0; j < n2; j++) {
	right[j] = arr[m+1+j];
	}
	int i=0, j=0, k=l;
	while (i<n1 && j<n2) {
	if(left[i]<=right[j]){
	arr[k] = left[i];
	i++;
	}else{
	arr[k] = right[j];
	j++;
	}
	k++;
	}
	while (i<n1) {
	arr[k] = left[i];
	i++;
	k++;
	}
	while (j<n2) {
	arr[k] = right[j];
	j++;
	k++;
	}
	}