Merge Two Sorted Arrays Without Using Extra Space [O(1)][Based on Insertion Sort][Simple Approach]

If we were allowed to use extra space then we can simply copy the elements of arr1[] (size n) and arr2[] (size m) into a new array arr3[] of size n+m and then sort the arr3[] and then recopy the elements into arr1[] and arr2[]. The time complexity of this approach would be O(n+m) (for copying) + O(nlogn) (for sorting) + O(n+m) (for recopying). The space complexity of this approach would be O(n+m) as we are creating an array of size m+n.

In this post I’ll go over Insertion sort type approach for merging two sorted array in O(1) space. Their is a more efficient approach known as Gap method the link to that approach is provided below —

Link to Gap method: https://hritikchaudhary.medium.com/merge-two-sorted-arrays-without-extra-space-efficiently-o-1-gap-method-detailed-simplified-57a336146601

Based on Insertion Sort — Simple Approach

Let’s see the algorithm for this approach —

1. Traverse the first array arr1[] and compare the i th element to the first element of second array arr2[].
2. If arr2[0] < arr1[i] is True, swap(arr2[0],arr1[i])
3. Re-sort the second array (put arr2[0] at it’s correct position)
4. If arr2[0] < arr1[i] is False, continue to the next element in arr1[]

C++ Code —

void merge(int arr1[], int arr2[], int n, int m)
{
 for (int i = 0; i < n; i++)
 {
  bool flag = 0;
  if (arr1[i] > arr2[0])
  {
   flag = 1;
   swap(arr1[i], arr2[0]);
  }
  if (flag)
  {
   sort(arr2, arr2 + m);
  }
 }
}

As we know that both the arrays are sorted, the only thing we need to do is to put all the elements in the correct position just like in the insertion sort. We will do this by comparing i th element of array arr1[] with the first element array arr2[] and if the first element of the second array is smaller than the i th element of the first array that means it will also be smaller than all the element on the right side of the i th element in the first array. Therefore, we will swap the first element of the second element with that i th element and resort the second array as after swapping second array will not be sorted anymore and that’s why we need to re-sort the array. Let’s take an example —

arr1[] = {1, 2, 8, 9, 12, 13}, n = 6

arr2[] = {3, 4, 7, 10}, m = 4

for i = 0 — arr2[0] = 3 and arr1[i] = 1 — First Iteration

is (arr2[0] < arr1[0])? — false

for i = 1 — arr2[0] = 3 and arr1[i] = 2 —Second Iteration

is (arr2[0] < arr1[1])? — False

for i = 2 — arr2[0] = 3 and arr1[i] = 8 — Third Iteration

is (arr2[0] < arr1[2])? — True

Therefore, we will swap arr2[0] with arr1[2] and arrays will become:

arr1[] = {1, 2, 3, 9, 12, 13}, n = 6

arr2[] = {8, 4, 7, 10}, m = 4

as we can see after swapping second array is not sorted anymore thus we need to re-sort the second array, after sorting —

arr1[] = {1, 2, 3, 9, 12, 13}, n = 6

arr2[] = {4, 7, 8, 10}, m = 4

for i = 3— arr2[0] = 4 and arr1[i] = 9 — Fourth Iteration

is (arr2[0] < arr1[3])? — True

Swap(arr2[0], arr1[3]) and Re-sort

arr1[] = {1, 2, 3, 4, 12, 13}, n = 6

arr2[] = {7, 8, 9, 10}, m = 4

for i = 4— arr2[0] = 7 and arr1[i] = 12 — Fifth Iteration

is (arr2[0] < arr1[4])? — True

Swap(arr2[0], arr1[4]) and Re-sort

arr1[] = {1, 2, 3, 4, 7, 13}, n = 6

arr2[] = {8, 9, 10, 12}, m = 4

for i = 5— arr2[0] = 8 and arr1[i] = 13 — Sixth Iteration

is (arr2[0] < arr1[5])? — True

Swap(arr2[0], arr1[5]) and Re-sort

arr1[] = {1, 2, 3, 4, 7, 8}, n = 6

arr2[] = {9, 10, 12, 13}, m = 4

OUTPUT

arr1[] = {1, 2, 3, 4, 7, 8}, n = 6

arr2[] = {9, 10, 12, 13}, m = 4

Time Complexity — O(n*m)

Space Complexity — O(1)

The worst case time complexity of code/algorithm is O(m*n). The worst case occurs when all elements of arr1[] are greater than all elements of arr2[].

Though it is not the best algorithm in terms of time complexity it is very simple to implement.

— Hritik Chaudhary