Merge sort is a sorting algorithm that uses "Divide and Conquer" method to sort the array.It divides the array into two halves and then recursively sort the two sub-array and then merge the two sorted sub-arrays into sequence.
Time complexity of Merge Sort is O(nLogn) in all 3 cases (worst, average and best).
Algorithm of merge sort ::
MergeSort(array, left, right)
If right > 1
Find the middle point to divide the array into two halves:
middle = (left+right)/2
Call mergeSort for first half:
MergeSort(array, left, middle)
Call mergeSort for second half:
MergeSort(array, middle+1, right)
Merge the two halves sorted in step 2 and 3:
MergeArray(array, left, middle, right)