You are given an array of integers. You have to sort the array using merge sort algorithm.

Input/Output Format For The Function:

**Input Format:**

The function contains a single argument, an integer array arr.

**Output Format:**

Return the sorted integer array.

We have provided a solution which contains necessary comments to understand the approach used:

**Description:**

We are given an input array of integers. Now we will implement merge sort algorithm to sort the integers in this array. Merge sort algorithm is a divide and conquer algorithm. Here, we partition the given array into subarrays, sort each of the subarrays separately and then merge these sorted subarrays to get the final resultant sorted array.

For more details, refer to the code given in recursive_solution.java.

Time Complexity (assuming that input arguments are already given and excluding time used in declaration of output):

O(n*logn) where n denotes the length of array arr.

Here we keep on splitting the array into halves until we reach an array of size 1. For each of these subarrays, we sort them separately and merge them. Hence, after sorting and merging all the subarrays, the time complexity turns out to be O(n*logn).

Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + Theta(n)

The above recurrence can be solved either using Recurrence Tree method or Master method. It** **falls in case II of Master Method and solution of the recurrence is Theta(n*logn).

Time complexity of MergeSort is Theta(n*logn) in all 3 cases (worst, average and best) as merge sort always divides the array into two halves and take linear time to merge two halves.

**Time Complexity:**

O(n*logn) where n denotes the length of array arr.

As time complexity assuming that input arguments are already given and excluding time used in declaration of output is O(n*logn), to read input it will take O(n) and to store output it will take O(n) hence total complexity will be O(n*logn) + O(n) + O(n) → O(n*logn).

**Auxiliary Space Used:**

O(n) + O(logn)where n denotes the length of array arr.

Here, Merge Sort space complexity will always be O(n) with arrays. If you draw the space tree out, it will seem as though the space complexity is O(n*logn). However, as the code is a Depth First code, you will always only be expanding along one branch of the tree, therefore, the total** **space usage required will always be bounded by O(3n) = O(n). Apart from this, at each step, the size of the array gets halved, the depth of the tree would be at most O(logn). So considering functional stack space used for recursive calls the overall auxiliary space turns out to be O(n) + O(logn).

**Space Complexity:**

O(n) + O(logn) where n denotes the length of array arr.

The input array is of size n, so the input space complexity is O(n), and auxiliary space used is O(n) + O(logn) and output uses O(n), hence total complexity will be O(n) + O(logn) + O(n) + O(n) → O(n) + O(logn).

`2) iterative_solution.java`

**Description:**

`We are given an input array of integers. Now the iterative approach of merge sort algorithm to sort given array. We start by dividing the array into blocks of size 1,2,4,8... and so on. For each of these blocks, we divide the array into corresponding subarrays of the size equal to block size and then sort them. Finally, we merge the sorted arrays and obtain the final sorted array. For more details, refer to the code given in iterative_solution.java.`

`Time Complexity (assuming that input arguments are already given and excluding time used in declaration of output):`

`O(n*logn) where n denotes the length of array arr.`

`Here we iterate over block sizes starting from 1 and then move on in multiples of 2, that is, 2, 4, 8... and so on. For each of these block sizes, we take 2 consecutive subarrays of that size over the entire array. So for a block size of 1, there will be 2 subarrays of size 1 and we then sort them separately and merge them. We do this over the entire array n. So for each block size, we require O(n) time to sort the subarrays and merge them. Hence, after sorting and merging all the subarrays, for all the block sizes, 1,2,4,8,...,log2(n) the time complexity turns out to be O(n*logn).`

**Time Complexity:**

`O(n*logn) where n denotes the length of array arr.`

`As time complexity assuming that input arguments are already given and excluding time used in declaration of output is O(n*logn), to read input it will take O(n) and to store output it will take O(n) hence total complexity will be O(n*logn) + O(n) + O(n) → O(n*logn).`

**Auxiliary Space Used:**

`O(n*logn) where n denotes the length of array arr.`

`Here, for each and every subarray, we create a new array and copy the corresponding elements from the original array into this new array. So, total space complexity required is O(n*logn).`

**Space Complexity:**

`O(n*logn) where n denotes the length of array arr.`

`The input array is of size n, so the input space complexity is O(n), and auxiliary space used is O(n*logn) and output uses O(n), hence total complexity will be O(n*logn) + O(n) + O(n) → O(n*logn).`

`Additional Material`

`QuickSort vs MergeSort:`

`Quicksort is an in-place sorting algorithm, that is, it does not require any extra space to perform sorting of an array. On the other hand, merge sort requires O(n*logn) auxiliary space. However, the worst-case time complexity of quicksort is O(n^2) because the time complexity depends on the selection of pivot. On the other hand, for mergesort, the worst-case time complexity is always O(n*logn).`

`Recommended Posts`

```
```