Last Updated: 8 Feb, 2021

Merge Sort In-Place

Easy

Asked in companies

Solve now

Problem statement

You are given an array consisting of N integers. Your task is to sort the array in non-descending order using merge sort. Perform the task as in-place.

Note:

In-place means that your implementation does not require extra memory for merge operation, unlike the standard implementation.

Example:

Let the array be [1, 2, -3, 4, -4, -5]. On sorting the array in non-descending order we get the resulting array [-5, -4, -3, 1, 2, 4].

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of elements present in the array.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, the resulting sorted array is printed.

Output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the sorted array.

Constraints:

1 <= T <= 10
1 <= N <= 5000
-10^5 <= Arr[i] <= 10^5

Where  ‘T’ represents the number of test cases and ‘N’ represents the number of elements present in the array.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The standard implementation of merge sort requires an extra temporary array for the merge operation to be performed in linear time.
We can avoid this extra space by effectively performing the merge sort in-place. But this would require us to move the elements within the original array.
The recursive calls of the merge sort implementation remain the same. The change is required only in the logic of merge procedure.
The idea behind this approach is to mark the starting and ending of the subarrays using two pointers, say start and end. Then iterate through both these subarrays simultaneously and in each iteration, we place the smaller of the two elements (present in each subarray) at its correct position in the sorted array.
Placing the element at the correct position may require shifting the later elements one step towards the right.
In this way, we can sort the array in-place using merge sort.

Algorithm for Merge Sort:

Let the recursive function be mergeSortHelper(array, left, right) which takes the given array, starting position of the subarray, and ending position of the subarray, respectively as its arguments.
Initially, we call the function as mergeSortHelper(arr, 0, N-1).
Base Condition: If left >= right, return.
We divide the array into two parts: arr[left, mid] and arr[mid +1, right], where mid = (left + right) / 2.
Recursively call the function on both the subarrays:
- mergeSortHelper(arr, left, mid)
- mergeSortHelper(arr, mid + 1, right)
Now, merge the two sorted subarrays by calling the merge function as merge(arr, left, mid, right). Here we do not pass the starting position of the second subarray, as it can be derived from the ending position of the first subarray.

Algorithm for Merge:

Let the function be merge(array, start, mid, end), which takes the array, starting position of the first sorted subarray, ending position of the first sorted subarray, and ending position of the second sorted subarray, respectively, as its arguments.
Let start2 be the starting position of the second subarray, where start2 = mid + 1.
If arr[mid] <= arr[start2], then the complete arr[start, end] is already sorted, so we can skip the merge procedure and just return.
Repeat the following steps until start <= mid AND start2 <= end:
- If arr[start] <= arr[start2]: then the element in the first subarray is the smaller one, and it is placed at the correct position. So, just increment start by one.
- Otherwise, the element in the second subarray is the smaller one. So, we need to place it at its correct position i.e. at index start.
  - Store a copy of arr[start2] in a temporary variable say, temp.
  - Now, shift all the elements from position start + 1 to start2 - 1, one step towards the right.
  - Place the element at its correct position, i.e., arr[start] = temp.
  - Increment the pointers start, mid, and start2 by one.

Solve now