Given two sorted arrays X[] and Y[] of size m and n each, merge elements of X[] with elements of array Y[] by maintaining the sorted order. i.e. fill X[] with first m smallest elements and fill Y[] with remaining elements.
The conversion should be done in-place and without using any other data structure.
Input:
X[] = { 1, 4, 7, 8, 10 }
Y[] = { 2, 3, 9 }
Output:
X[] = { 1, 2, 3, 4, 7 }
Y[] = { 8, 9, 10 }
The idea is very simple. We consider each element of array X[] and ignore the element if it is already in correct order (i.e. the element smallest among all remaining elements) else we swap it with smallest element which happens to be first element of Y. After swapping, we move the element (now present at Y[0]) to its correct position in Y[] to maintain the sorted order. The merge process is almost similar to merge routine of mergesort algorithm. The only difference is that we are not using an auxiliary array for merging.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <algorithm> using namespace std; // Utility function to print contents of an array void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << '\n'; } // in-place merge two sorted arrays X[] and Y[] // invariant: X[] and Y[] are sorted at any point void merge(int X[], int Y[], int m, int n) { // consider each element X[i] of array X and ignore the element // if it is already in correct order else swap it with next smaller // element which happens to be first element of Y for (int i = 0; i < m; i++) { // compare current element of X[] with first element of Y[] if (X[i] > Y[0]) { swap(X[i], Y[0]); int first = Y[0]; // move Y[0] to its correct position to maintain sorted // order of Y[]. Note: Y[1..n-1] is already sorted int k; for (k = 1; k < n && Y[k] < first; k++) { Y[k - 1] = Y[k]; } Y[k - 1] = first; } } } // main function int main() { int X[] = { 1, 4, 7, 8, 10 }; int Y[] = { 2, 3, 9 }; int m = sizeof(X) / sizeof(X[0]); int n = sizeof(Y) / sizeof(Y[0]); merge(X, Y, m, n); cout << "X: "; printArray(X, m); cout << "Y: "; printArray(Y, n); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.Arrays; class Merge { // in-place merge two sorted arrays X[] and Y[] // invariant: X[] and Y[] are sorted at any point public static void merge(int[] X, int[] Y) { int m = X.length; int n = Y.length; // consider each element X[i] of array X and ignore the element // if it is already in correct order else swap it with next smaller // element which happens to be first element of Y for (int i = 0; i < m; i++) { // compare current element of X[] with first element of Y[] if (X[i] > Y[0]) { // swap (X[i], Y[0]) int temp = X[i]; X[i] = Y[0]; Y[0] = temp; int first = Y[0]; // move Y[0] to its correct position to maintain sorted // order of Y[]. Note: Y[1..n-1] is already sorted int k; for (k = 1; k < n && Y[k] < first; k++) { Y[k - 1] = Y[k]; } Y[k - 1] = first; } } } // main function public static void main (String[] args) { int[] X = { 1, 4, 7, 8, 10 }; int[] Y = { 2, 3, 9 }; merge(X, Y); System.out.println("X: " + Arrays.toString(X)); System.out.println("Y: " + Arrays.toString(Y)); } } |
Output:
X: 1 2 3 4 7
Y: 8 9 10
The time complexity of above solution is O(mn) and auxiliary space used by the program is O(1). The problem can in fact be solved in linear time and constant space. This approach highly complicated and is discussed here. Thanks to Tim for suggesting this optimized approach in comments.
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
This is a nice algorithm, but linear-time, constant-space (but extremely complicated) algorithms do in fact exist — see for example http://www.akira.ruc.dk/%7Ekeld/teaching/algoritmedesign_f04/Artikler/04/Huang88.pdf. (Though I certainly would not expect anyone to describe this algorithm in an interview situation!)
Thanks Tim for suggesting this optimized approach. We have added this in post. Please let us know if you find any more interesting methods to solve any problem. Happy coding!
this can be O(m + n) time complexity.
It sounds simpler to just run heap sort on top of a wrapper of two arrays totally ignoring the sorted order, it runs in O((m+n)*log(m+n)) instead of O(mn).
That won’t be in-place right?
Why not? Heap sort works in-place. Quick sort will do too. It only needs to map indices to either x or y depending on whether the current index k is greater than m-1 (return &(x+k)) or not (return &(y+(k-m)))