MergeSort – A nlogn time sorting algorithm

MergeSort is a Divide and Conquer based algorithm just like QuickSort, with best and worst-case sorting time complexity nlogn. MergeSort works by repeatedly diving the input array into subarray until each subarray doesn’t have only 1 element and then merging those subarrays in such a way that, the final result of combination is a sorted list.

As you can see from the following example array  {38, 27, 43, 3, 9, 82, 10}, the mergesort first keeps on repeatedly dividing the given array into two halves until every subarray is not consisting only single element. The division procedure is highlighted using a red color.

Once this state has reached, then mergesort them start merging the subarrays (in the same order in which they were divided) but in sorted order. The division procedure is highlighted using the green color.

Algorithm

Algorithm for MergeSort 

MergeSort(arr[], start, end){
    if(start<end)
        //find the middle element of the current array
        middle = (start+end)/2;
        //divide current array into two halves at middle
        mergesort(arr[], start, middle)
        mergesort(arr[], middle+1, end)
        //merge the left and right array
        merge(arr[], start, middle, end);
}

Implementation of MergeSort in CPP

#include <bits/stdc++.h>
using namespace std;

int merge(int *arr, int start, int middle, int end){

	int i,j,k,n,m;
	n = middle - start + 1;
	m = end - middle;
	
	int left[n], right[m];

	for(int i=0; i<n; i++)
		left[i] = arr[start+i];
	for(int j=0; j<m; j++)
		right[j] = arr[middle+j+1];
	
	k=start;
	i=0;
	j=0;

	while(i<n && j<m){
		if(left[i]<right[j]){
			arr[k] = left[i];
			i++;
		}
		else{
			arr[k] = right[j];
			j++; 
		}
		k++;
	}

	while(i<n){
		arr[k] = left[i];
		i++;
		k++;
	}

	while(j<m){
		arr[k] = right[j];
		j++;
		k++;
	}

	return 0;
}


int MergeSort(int *arr, int start, int end)
{
	if(start<end){
		int middle = (start+end)/2;
		MergeSort(arr, start, middle);
		MergeSort(arr, middle+1, end);

		merge(arr, start, middle, end);
	}

	return 0;
}

int main()
{

	int arr[] = {38, 27, 43, 3, 9, 82, 10};
	int size = sizeof(arr)/sizeof(arr[0]);

	MergeSort(arr, 0, size-1);

	cout<<"Sorted array is:"<<endl;
	for(int i=0; i<size; i++)
		cout<<arr[i]<<" ";
	cout<<endl;

	return 0;
}

Output

Sorted array is:
3 9 10 27 38 43 82

Time Complexity

The Best and Worst-case time complexity of MergeSort is O(NlogN), where N is the number of elements in the input array.

Recurrence relation for MergeSort is

T(n) = T(n/2) + O(n)
here n is the number of elements to be sorted.

MergeSort properties at a glance:

1. Best case time complexity = O(NlogN)
2. Worst-case time complexity = O(NlogN)
3. Auxiliary space requirement = O(N)
4. Number of comparisons in best case = O(NlogN)
5. Number of comparisons in worst case = O(NlogN)
6. Merge Sort is a stable sort

Did, we miss something, or do you want to add some other key points?
Please comment.