**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 arraymiddle = (start+end)/2;//divide current array into two halves at middlemergesort(arr[], start, middle) mergesort(arr[], middle+1, end)//merge the left and right arraymerge(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.