Merge Sort

It’s sorting algorithm which is based on Divide and Conquer algorithm. So basically it divides the input array into two halves ,calls itself for the two halves, then we will merge two sorted halves.

The merge() function is used for merging two halves. First half is from [lo,mid] and second half is from [mid+1,hi].Here we will have these two halves sorted.

Merge sort tree

CODE:

Time Complexity: O(NlogN)

Space Complexity: O(N)

Stack Space (Number of levels of recursion):O(logN)

Thank You !