# Merge Sort

## #

Overview- Time Complexity:
`O(nlogn)`

in all scenarios - Space Complexity:
`O(n + log(n))`

simplified to`O(n)`

- Not In-Place
- Stable

## #

General IdeaMerge sort is a divide and conquer technique. Given an array, we repeatedly divide it into 2 arrays, till we have one element of concern. At the point, that single element will be sorted.

Now, we proceed to merge the divided sections of the array. When merging, we create a temporary array to hold the items from the 2 arrays we are merging. We will have 2 pointers `i`

and `j`

to track the current index of array 1 and array 2. In each iteration, we compare the index pointed to by the pointer `i`

in array 1 to that of the index of array 2 by pointer `j`

. Whichever element is the smaller one, we copy that into the temporary array.

At the end of the merge process, there maybe left over elements in either array, so we just copy them over into the temporary array. At the end of the merge process, we would have merged both arrays into one sorted array.

Now, we need to copy whatever elements are in the temporary array back into the original array starting from index `i`

.

## #

Time ComplexityTime taken to merge 2 portions of the array will be `O(n)`

.

Let mergeSort take a time complexity of `T(n)`

. Due to the 2 calls to mergeSort for the 2 halves of the array and subsequently to merge function which takes `O(n)`

, `T(n)`

can be represented as follows:

`T(n) = 2 * T(n/2) + O(n)`

For every call to `merge()`

, there will be a time complexity of `O(n)`

. We are making `log(n)`

such calls due to the depth of the recursive call stack.

Therefore, `T(n)`

simplifies to an order of `O(nlogn)`

.

Note: There is no best/worst case for merge sort. Therefore, despite the initial condition of the list, already sorted, reverse sorted etc., merge sort will still take the same time complexity of `O(nlogn)`

.

Reference: https://www.youtube.com/watch?v=sfmaf4QpVTw&t=104s

## #

Space ComplexityNote that merge sort is __not an in-place sort__, which means it requires extra space. This extra space is required in the merge algorithm where we need to copy the elements from the original array into a temporary array. This takes `O(n)`

space.

Apart from a temporary, we also need to consider the recursion stack involved. Note that thought each call to `mergeSort`

has 3 sub-functions, not all the recursive calls occur simultaneously. Since it is a divide and conquer algorithm, we need `ceil(log(n)) + 1`

, which simplifies to `O(log(n))`

space for the stack.

The total space complexity is therefore given by `O(n + log(n))`

which is dominated by the `O(n)`

term, and hence simplifies to `O(n)`

.