Merge Two Sorted Arrays Without Extra Space

Approach:

We want to have the ‘N’ smallest elements in ‘A’. For the ‘ith’ smallest elements we can traverse over the remaining positions of ‘A’ and the array ‘B’ to find the minimum elements among them, and then swap that element with ‘A[i]’. Lastly, we sort the array ‘B’.  
 

Algorithm:

• for ‘i’ from 0 to ‘N - 1’:
  • Flag = i
  • Least = A[i]
  • for ‘j’ from ‘i’ to ‘N - 1’:
    • if(A[j] < Least):
      • Least = A[j]
      • Flag = j
  • for ‘j’ from ‘0’ to ‘M - 1’:
    • if(B[j] < Least):
      • Least = B[j]
      • Flag = j
  • Swap ‘A[i]’ with the ‘Least’ element.
• Sort the array ‘B’.

Approach:

Here, we will keep the ‘N’ smallest numbers in ‘A’ (not necessarily sorted) and the rest in ‘B’ (not necessarily sorted). We iterate over ‘A’ and ‘B’ using two pointers ‘i’ = 0 and ‘j’ = 0 respectively. If ‘A[i]’ is greater than or equal to ‘B[j]’. We swap some ‘kth’ element of ‘A’ with ‘B[j]’ and increment ‘j’, else we increment ‘i’. It makes sense to always replace the largest elements of ‘A’. Hence, we initialize ‘k’ = ‘N - 1’. Then, we decrement ‘k’ after each swap. Lastly, we sort ‘A’ and ‘B’.

Algorithm:

• i = 0, j = 0, k = N - 1
• while(i <= k and j < M):
  • if(A[i] < B[j]):
    • i++
  • else
    • swap(A[k], B[j])
    • j = j + 1
    • k = k - 1
• Sort ‘A’ in non-decreasing order.
• Sort ‘B’ in non-decreasing order.

Approach:

• We want to perform the swaps in such a way that we don’t have to sort the arrays in the end. We want to fill the smallest numbers in the smallest positions instead of putting them in the last positions like in Approach 2 (i.e., we want to start with ‘k’ = 0 instead of ‘k’ = ‘N - 1').  However, in this case, it is possible that a number from ‘A’ is replaced by some number from ‘B’ however, it is possible that it may be utilized at some later position in ‘A’. So, we need a way to extract the number which was initially placed at a position ‘k’ in case it was replaced earlier.
• We can use Euclid’s Lemma in the following way:
  • From a number L = X*Z + Y, we can get ‘X’ by dividing ‘L’ by ‘Z’ and ‘Y’ by taking the modulo of ‘L’ by ‘Z’.
  • We choose ‘MX’ = 10^9 + 1 as ‘Z’ for the entire array ‘A’. We choose this number because of the constraints on elements of ‘A’ and ‘B’.
• We iterate through ‘A’ and ‘B’ using two pointers ‘i’ and ‘j’ and initialize the positions by ‘k’ = 0. We check for the initially placed numbers at ‘A[i]’ and ‘B[j]’. We compare them and increment ‘A[k]’ or ‘B[k - n]’ by the product of the minimum of the two original numbers and ‘MX’. We increment ‘j’ if the number from ‘B’ was smaller, else we increment ‘i’.
• Likewise, we update the values for all ‘k’ from 0 to ‘N + M - 1’.
• Lastly, we iterate through ‘A’ and ‘B’ and divide all numbers by ‘Z’ to get the merged array.
   

Algorithm:

• MX = 10^9 + 1
• i = 0, j = 0, k = N - 1
• while(i < N and j < M and k < N + M):
  • OriginalNumberA = A[i] % MX
  • OriginalNumberB = B[j] % MX
  • if(OriginalNumberA <= OriginalNumberB):
    • if(k < n):
      • A[k] += OriginalNumberA * MX
    • else:
      • B[k - N] += OriginalNumberA * MX
    • i = i + 1
    • k = k + 1
  • else:
    • if(k < N):
      • A[k] += OriginalNumberB * MX
    • else:
      • B[k - N] += OriginalNumberB * MX
    • j = j + 1
    • k = k + 1
• while(j < M):
  • OriginalNumberB = B[j] % MX
  • if(k < N):
    • A[k] += OriginalNumberB * MX
  • else:
    • B[k - N] += OriginalNumberB * MX
  • j = j + 1
  • k = k + 1
• while(i < N):
  • OriginalNumberA = A[i] % MX
  • if(k < N):
    • A[k] += OriginalNumberA * MX
  • else:
    • B[k - N] += OriginalNumberB * MX
  • i = i + 1
  • k = k + 1
• for ‘i’ from 0 to ‘N - 1’:
  • A[i] = A[i] / MX
• for ‘j’ from 0 to ‘M - 1’:
  • B[j] = B[j] / MX