Merge Sort🎂

Merge sort is a sorting algorithm used to sort an array/list.

Time Complexity
The time complexity of the merge case is O(n log n) in all the cases.

Explanation
In merge sorted we use the divide and conquer method to divide the whole list into sub-partitions until each partition only contains one element, so that takes O(log n) time. Second, on each level of the Recursion tree, we perform the merge operation that goes through the n elements in the list and sorted them, so that takes O(n). So combining both operations we get O(n log n).

Code