**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

##### 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.