Merge two sorted arrays

Recently, I came across this question & it beat the shit out of me.

Let’s just understand the logic & implement it.

Problem Statement :

Given two sorted integer arrays X and Y merge Y into X as one sorted array.

Note:

• The number of elements initialized in X and Y are m and n respectively.
• You may assume that X has enough space (size that is equal to m + n) to hold additional elements from Y.

The idea is simple. We consider each element of X[] and ignore the element if it is already in correct order. (i.e. the element smallest among all remaining elements) else we will swap it with the smallest element which happens to be the first element of Y[].

After swapping, we move the element Y[0] to its correct position in Y[] to maintains the sorted order. And after this, the merge process is similar to the merge process of merge sort algorithm. The only difference is we are not using auxiliary array for merging.

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;
}
}
}

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));
}
}