Merge Sort

Easy
0/40
Average time to solve is 15m
profile
Contributed by
222 upvotes
Asked in companies
Thought WorksAccentureInfosys

Problem statement

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

subsequence

The above illustrates shows how merge sort works.
Note :
It is compulsory to use the ‘Merge Sort’ algorithm.
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2*'T' lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘N’ which denotes the size of ‘ARR’.

The second line of each test case contains ‘N’ space-separated elements of ‘ARR’. 
Output Format :
For each test case, print the numbers in non-descending order
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= N <= 10^4
-10^9 <= arr[i] <= 10^9

Time Limit : 1 sec
Sample Input 1 :
2
7
3 4 1 6 2 5 7
4
4 3 1 2
Sample Output 1 :
1 2 3 4 5 6 7
1 2 3 4
Explanation For Sample Input 1:
Test Case 1 :

Given ‘ARR’ : { 3, 4, 1, 6, 2, 5, 7 }

Then sorted 'ARR' in non-descending order will be : { 1, 2, 3, 4, 5, 6, 7 }. Non-descending order means every element must be greater than or equal to the previse element.

Test Case 2 :

Given ‘ARR’ : { 4, 3, 1, 2 }

Then sorted 'ARR' in non-descending order will be : { 1, 2, 3, 4 }. 
Sample Input 2 :
2
4
5 4 6 7
3
2 1 1
Sample Output 2 :
4 5 6 7
1 1 2
Hint

Try to think recursively.

Approaches (2)
Recursion

The basic idea is that we divide the given ‘ARR’ into two-part call them ‘leftHalves’ and ‘rightHalves’ and call the same function again with both the parts. In the end, we will get sorted ‘leftHaves’ and sorted ‘righthalves’ which we merge both of them and return a merged sorted ‘ARR’.

We implement this approach with a divide and conquer strategy.

 

Here is the algorithm : 

 

  1. Divide ‘ARR’ into two-part ‘leftHalves’ and ‘rightHalves’ and the size of both parts are almost equal means ‘leftHalves’ can have one size extra comparing to ‘rightHalves’
    • Recursively solve for ‘leftHalves’
    • Recursively solve for ‘rightHalves’
  2. In the recursive part, every time we will get some part of ‘ARR’. Then divide it into two parts until the size of each subarray is not equal to 1.
  3. In the return part, we get two sorted arrays ‘leftHalves’ and ‘rightHalves’ using recursion.
  4. After getting both sorted parts, we merge both of them in such a way so that we get a merged sorted array.

 

MERGE() function :

  1. Suppose we have two sorted arrays ‘leftHalves’ and ‘rightHalves’ then we merge both of them into ‘mergedArr’
  2. Currently, we have two pointers ‘ptrLeft’ and ‘ptrRight’, and both are pointing to starting indices of ‘leftHalves’ and ‘rightHalves’.
    • If ‘leftHalves[ptrLeft] < rightHalves[ptrRight]’ then add ‘leftHalves[ptrLeft]’ in ‘mergeArr’ and increase ‘ptrLeft’ by one.
    • Else add ‘rightHalves[ptrRight]’ in ‘mergeArr’ and increase ‘ptrRight’ by one.
  3. Add remaining elements from ‘leftHalves’ and ‘rightHalves’.
  4. Copy ‘mergeArr’ elements to ‘ARR’.
Time Complexity

O(N*log(N)), where ‘N’ is a number of elements in ‘ARR’.

 

We divide our ‘ARR' into two parts and then merge them. Merging of arrays can take maximum O(N) time. Therefore, the recurrence relation for merge sort is : T(N) = 2T(N/2) + O(N).

This relation can be solved using ‘Master Theorem’ which gives time complexity as O(N*log(N)). Hence, the overall time complexity will be O(N*log(N))

Space Complexity

O(N), where ‘N’ is the number of elements in ‘ARR’.

 

We use 2 temp arrays to store the elements of ‘ARR’ whose size can ‘N’ in worst case. Recursive stack can be called maximum ‘N’ times as the size of ‘ARR’ is ‘N’. Hence, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Merge Sort
Full screen
Console