Merge Sort, Its not hard!

Merge sort works on the principle of divide and conquer algorithm. It is one of the most efficient sorting algorithm. The top down merge sort approach uses recursion. We break/divide the array into subparts (till single element).

This sorting algorithm recursively sorts the subparts and then merges them into a single sorted array.

There are 4 important points where all the process of merge sort takes place:

1. Find the middle element of the array.
2. Call mergeSort function for the first half.
3. Call mergeSort function for the second half.
4. Merge the two halves into a single sorted array, and yes, this is the answer! Ain't that easy? it is!

Below is the function mergeSort() in C++ language:

Time Complexity:

Total T(n) work is done which is divided as:

1. k amount of constant work,
2. T(n/2) work for 2 halves,
3. Merge two halves = k1n,
4. Copy elements to input array = k2n, So, T(n) = k + T(n/2) + T(n/2) + k1n + k2n T(n) = 2T(n/2) + Kn {K here is the sum of all constants - k, k1, k2}

The recurrence relation that we'll get-
T(n) = 2T(n/2) + Kn
After solving this recurrence relation, we'll come to the conclusion that the time complexity for merge sort is-
O(nlogn)

Space Complexity:

Space complexity is the maximum space required at any point of time during execution of a program.
In merge sort, we use recursion on half part of the array, So the calling will be done as (n is size of the array):
n -> n/2 -> n/4 -> n/8 ... and so on
that is, logn function waiting in the call stack.
-> klogn space for storing functions
-> kn for array
So the maximum space required is kn,
Space Complexity will be O(n).

I hope now you can do problems on merge sort :)