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

1. Find the middle point to divide the array into two halves:
   middle = (left+right)/2

2. Call mergeSort for first half:
   MergeSort(array, left, middle)

3. Call mergeSort for second half:
   MergeSort(array, middle+1, right)

4. Merge the two halves sorted in step 2 and 3:
   MergeArray(array, left, middle, right)

For eg.:

                 5    4     2     6     1     3    2    6           unsorted array
                         /\                         /\              divide
             | 5  4      2  6  |             | 1   3     2    6 |
                /\         /\                   /\         /\       divide
            | 5  4 |    | 2   6 |             | 1  3 |  |  2    6 |
                /\          /\                     /\          /\   divide
           | 5 | | 4 |  | 2 | | 6 |          | 1 | |  3 |  | 2 | |  6 |
                \/          \/                    \/           \/   merge
             | 4  5 |    | 2  6 |             | 1   3 |    | 2   6 |
                      \/                                \/          merge
                | 2   4   5  6 |                |  1   2   3   6 |
                                       \/                           merge
                    | 1    2     2     3    4     5    6    6 |     sorted array