Merge Sort

This is an algorithm based on the divide and conquer principle. The algorithm divides the problem of sorting an array into smaller problems of sorting smaller arrays. These smaller sorted arrays are then merged into bigger sorted arrays in the conquer phase until we have a completely sorted array.

Time Complexity: O(nlogn) - From the recurrence tree of this algorithm, there are atmost logn levels of this binary tree. The cost of merging the small sorted arrays is n at each level, thus nlogn.

Space Complexity: O(nlogn)