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:

- Find the middle element of the array.
- Call mergeSort function for the first half.
- Call mergeSort function for the second half.
- 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:

- k amount of constant work,
- T(n/2) work for 2 halves,
- Merge two halves = k1n,
- 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 :)

## Discussion (0)