Merge two arrays by satisfying given constraints

Given two sorted arrays X[] and Y[] of size m and n each where m >= n and X[] has exactly n vacant cells, merge elements of Y[] in their correct position in array X[] i.e. merge (X, Y) by keeping the sorted order.

 

For example,


Input:
X[] = { 0, 2, 0, 3, 0, 5, 6, 0, 0}
Y[] = { 1, 8, 9, 10, 15 }

The vacant cells in X[] is represented by 0

Output:
X[] = { 1, 2, 3, 5, 6, 8, 9, 10, 15 }

 

The idea is very simple. We initially move non-empty elements of X[] in the beginning of X[] and then merge X[] with Y[] starting from end. The merge process is similar to merge routine of the mergesort algorithm.

C

Download   Run Code

Java

Download   Run Code



Output:


1 2 3 5 6 8 9 10 15

 
The time complexity of above solution is O(m + n) and auxiliary space used by the program is O(1).

 
Exercise: Merge arrays in descending order

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
oerpli
Guest
oerpli

In the merge part you first merge from both arrays and then fill up from the second.
This can also done with the following code, which takes elements from both arrays until k = 0: