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,

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

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.


Download   Run Code


Download   Run Code


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

newest oldest most voted
Notify of

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: