Merging Two Sorted Arrays Without Extra Space

In this problem, we will be given two sorted arrays. Our task is to merge the given two arrays. However, the constraint is that we have to merge them without using any extra space. Thus, after sorting the arrays, the initial elements will be in the first array (according to the initial capacity of the first array), and the remaining elements in the second array.

Let us see some examples to understand the input and output of the program.

Examples:

Input: array1 = [11], array2 = [3, 4]

Output: array1 = [2], array2 = [4, 11]

Input: array1 = [1, 6, 9, 11, 16, 21], array2 = [1, 4, 7, 13]

Output: array1 = [1, 1, 4, 6, 7, 9], array2 = [11, 13, 16, 21]

The task would have been easy if we were allowed to use extra space. Though, solving this problem without extra space makes it complicated.

The brute force approach will solve this problem in O(m * n) time complexity. However, there are efficient approaches to solving it.

Approach - 1

We will follow this method to solve this problem:

We will begin iterating from the last element of the second array array2 and search if it is available in array1. If we find an element in array1 greater than that element, we will move the last element to the first array array1 and the other element in array2. To keep the two arrays sorted, we must insert the elements in the proper position. We can use the Insertion Sort algorithm to search for this correct position.

Below is the algorithmic approach to solving this problem:

• We will iterate over every element of the second array starting from the end of this array.
• For every element of the second array, perform these steps
  • We will store the last element of the first array in a variable: last = array1[-1]
  • Iterate over the first array starting from the last second element until we meet the condition that array1[j] < array2[i].
  • Now we will move the elements of the first array one index ahead.
  • We will check if the last element of the first array is greater than the last element of the second array then we will swap the elements at these positions.
• Lastly, we will print the merged sorted arrays.
• In the second loop, the elements of the individual array are always maintained in the sorted order.

Below is the Python program for the implementation of the approach mentioned above.

Code

Output:

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21

Time Complexity: This program will take O(M * N) to complete. The time complexity is non-linear because we are iterating over both arrays in a nested loop.

Auxiliary Space: Since the problem itself states to solve it by taking only constant extra space. Hence, the space complexity is O(1).

Approach - 2

Now we will discuss another efficient approach to solve this problem.

There is a pattern repeating itself in the above solution. When traversing both sorted arrays simultaneously, suppose we reach the jth element of the second sorted array, which is smaller than the ith element of the first sorted array. Then in the next step, we have to insert the jth element in the first array, remove some kth element from the first array and insert it into the second array. We will use this pattern to optimize the above code.

Here are the steps that we will follow to solve the problem:

• We will initialize three variables, i = 0, j = 0, and k = n - 1. Here n is the size of the first array.
• We will iterate over every element of array1 and array2. However, we will use each array's two i and j pointers this time.
  • Now we will check if the ith element of the first array is smaller than the jth element of the second array, then increment i.
  • Else if the above condition is not satisfied, we will replace the kth element of the first array with the jth element of the second array. Increase i by one and decrease k by 1.
• The last step is to sort the individual arrays after swapping the two elements to maintain the order.

Below is the Python program for the above algorithm

Code

Output:

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 2 
4 7 13  
Merged First Array: 1 
2 4 6 
7 9  
Merged Second Array: 11 
13 16 21  

Time Complexity: This program will take O((N + M) * log(N + M)) time to complete. Here N and M are the sizes of the two arrays. We are iterating the list only once (N + M); however, we are sorting the arrays at the end of every iteration; therefore, the linear time is multiplied by log(N + M).

Space Complexity: Since the program is not taking any extra space, O(1).

Approach - 3

We will solve this problem using this approach:

This approach will compare the first array's last element with the second array's first element. Now, if the element of the first array is greater than that of the second array, we will swap the two elements. The next step is the sorting of the arrays. The first array is already sorted, but we have the second one. We have to repeat these steps until the first condition is true. At the end of the process, we will get two sorted arrays.

We will follow the steps below for this approach.

• We will initialize a variable i as 0.
• We will start a while loop until the last element of the first array is greater than the second array's first element.
  • If the ith element of the first array is greater than the first element of the second array.
  • We will swap the ith element and the 0th of the two arrays
  • Then we will sort the second array
  • The next step is to increment i by 1
• At last, we will print both arrays.

Below is the Python program to solve the problem with the abovementioned approach.

Code

Output:

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21 

Time Complexity: This program will take O(M * (N * logN)) time complexity. Here M and N are the sizes of the two arrays. LogN time complexity is for sorting the second array at the end of every iteration.

Auxiliary Space: The space complexity is the same as O(1).

Approach - 4

Below is another approach to solving the problem.

• We will take the length of the shorter array as N and the length of the larger array as M.
• We will take the shorter array and find the index at which we should partition it.
• We have to partition the shorter array at the point where its median lies. (m1)
• Now we will take the second array's first M - m1 elements.
• We will compare the border elements.
  • If the m1 element is less than the f1 element and the l2 element is less than the f2 element, then we have found the index.
  • Else if the m1 element is greater than the f2 element, then we need to search in the left subarray.
  • Else we will search in the right subarray.
• The next step is to store all the smallest elements in the array that is shorter in length.
• Till index i, we will swap all the elements of the shorter array with the larger array's first M - i elements.
• The next step is to sort the two arrays.
• If the length of the first array is greater than the length of the second array, then all the smaller elements will be moved to the first array.
• Then we will rotate the larger array N times in a counter-clockwise direction.
• The last step is to swap both arrays' first N elements.

Below is the Python code for the implementation of the approach mentioned above.

Code

Output:

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21  

Time Complexity: This program will take O(max(M * logM, N * logN)) time to complete. Here log time complexity is for sorting the two arrays after each iteration.

Space Complexity: This program will take up constant extra space. Hence, O(1)

Approach - 5

In this approach, we will merge the two sorted arrays using the insertion sort.

In the above program, when we insert the elements in other arrays, we can use the insertion sort to insert the elements, as the rest of the arrays are already sorted. This will further reduce the time complexity of the program. Hence, when swapping the two elements, we have to put the swapped elements in the position so that the array is still sorted. This can be done using a single traversal.

Below are the steps that we will follow to solve the problem:

• We will sort the first list by continuously comparing the list with the first element of the second list. If the element of the second list is greater than that of the first list, then we will swap the two elements.
• When we swap an element, we will insert the swapped element in the second list using the insertion sort method. In this way, the element will always be inserted in the correct position, and at the end of the iterations, the second list will always be sorted.
• Since we are performing swapping, if we find an element of the second list greater than the element of the first list, swapping the two elements will always keep the first list sorted. However, we can maintain the order in the second list by performing insertion sort.

Below is the Python program to solve the problem using the above approach.

Code

Output:

Initial First Array: [1, 6, 9, 11, 16, 21]
Initial Second array: [1, 4, 7, 13]
Merged First Array: [1, 1, 4, 6, 7, 9]
Merged First Array: [11, 13, 16, 21]

Time Complexity: This program has a non-linear time complexity. The time complexity is O(M * N). Here, M and N are the lengths of the two given arrays.

Space complexity: Space complexity is the required constant space complexity. Hence, it is O(1).

Approach - 6

We will use the Euclidean Division Lemma to merge the two arrays in this approach. This lemma is stated as (((Operation_on_array) % A) * A)

Below are the steps we need to follow to solve this problem:

• We will use the same approach we used while merging the arrays using the merge sort. However, this time we will use the Euclidean Division Lemma simultaneously with the previous approach.
• After merging both arrays, we will divide both of them with A
• Here A is a number greater than all the elements of both arrays.
• In our problem, there is no upper limit to the elements of the arrays. To maintain generality, we will take A as 10e7 + 1.

Below is the Python program to solve this problem using Euclidean Division Lemma.

Code

Output:

Initial First Array: 1 
6 9 11 
16 21  
Initial Second array: 1 
4 7 13  
Merged First Array: 1 
1 4 6 
7 9  
Merged First Array: 11 
13 16 21  

Time Complexity: Since we are using linear loops, the time complexity of this program will be O(M + N)

Space Complexity: O(1)