Merge two sorted arrays from their end

Given two sorted integer arrays, merge them into a single array in decreasing order, and return it. In other words, merge two sorted arrays from their end.

For example,

Input:

X = [1, 3, 5]
Y = [2, 6, 7]

Output: [7, 6, 5, 3, 2, 1]

Input:

X = [1, 4, 7, 8]
Y = [2, 3, 9]

Output: [9, 8, 7, 4, 3, 2, 1]

Practice this problem

We can easily solve this problem iteratively. There are many cases to deal with – either X or Y may be empty during processing, either X or Y can run out first, and finally, there is a challenge of starting the result array empty, and building it up while traversing X and Y in reverse order.

Following is the C++, Java, and Python implementation that handles all these cases:

C++

#include <iostream>

#include <vector>

using namespace std;

// Utility function to print contents of a vector

void printArray(vector<int> &arr)

{

for (int i: arr) {

cout << i << " ";

}

cout << endl;

}

// Function to merge two sorted vectors X[] and Y[] from their end

vector<int> merge(vector<int> const &X, vector<int> const &Y)

{

int i = X.size() - 1, j = Y.size() - 1;

vector<int> aux(X.size() + Y.size());

int k = 0;

// while there are elements in the first and second arrays

while (i >= 0 && j >= 0)

{

if (X[i] >= Y[j]) {

aux[k++] = X[i--];

}

else {

aux[k++] = Y[j--];

}

// copy remaining elements

while (i >= 0) {

aux[k++] = X[i--];

}

while (j >= 0) {

aux[k++] = Y[j--];

}

return aux;

}

int main()

{

vector<int> X = { 1, 4, 7, 8 };

vector<int> Y = { 2, 3, 9 };

vector<int> aux = merge(X, Y);

cout << "First Array : "; printArray(X);

cout << "Second Array: "; printArray(Y);

cout << "After Merge : "; printArray(aux);

return 0;

}

Download Run Code

Output:

First Array : 1 4 7 8
Second Array: 2 3 9
After Merge : 9 8 7 4 3 2 1

Java

import java.util.Arrays;

class Main

{

// Function to merge two sorted arrays X[] and Y[] from their end

public static int[] merge(int[] X, int[] Y)

{

int i = X.length - 1, j = Y.length - 1;

int[] aux = new int[X.length + Y.length];

int k = 0;

// while there are elements in the first and second arrays

while (i >= 0 && j >= 0)

{

if (X[i] >= Y[j]) {

aux[k++] = X[i--];

}

else {

aux[k++] = Y[j--];

}

// copy remaining elements

while (i >= 0) {

aux[k++] = X[i--];

}

while (j >= 0) {

aux[k++] = Y[j--];

}

return aux;

}

public static void main (String[] args)

{

int[] X = { 1, 4, 7, 8 };

int[] Y = { 2, 3, 9 };

int[] aux = merge(X, Y);

System.out.println("First Array : " + Arrays.toString(X));

System.out.println("Second Array: " + Arrays.toString(Y));

System.out.println("After Merge : " + Arrays.toString(aux));

}

Download Run Code

Output:

First Array : [1, 4, 7, 8]
Second Array: [2, 3, 9]
After Merge : [9, 8, 7, 4, 3, 2, 1]

Python

# Function to merge two sorted lists `X` and `Y` from their end

def merge(X, Y):

i = len(X) - 1

j = len(Y) - 1

aux = [0] * (len(X) + len(Y))

k = 0

# while there are elements in the first and second arrays

while i >= 0 and j >= 0:

if X[i] >= Y[j]:

aux[k] = X[i]

i = i - 1

else:

aux[k] = Y[j]

j = j - 1

k = k + 1

# copy remaining elements

while i >= 0:

aux[k] = X[i]

k = k + 1

i = i - 1

while j >= 0:

aux[k] = Y[j]

k = k + 1

j = j - 1

return aux

if __name__ == '__main__':

X = [1, 4, 7, 8]

Y = [2, 3, 9]

aux = merge(X, Y)

print('First Array :', X)

print('Second Array:', Y)

print('After Merge :', aux)

Download Run Code

Output:

First Array : [1, 4, 7, 8]
Second Array: [2, 3, 9]
After Merge : [9, 8, 7, 4, 3, 2, 1]

The time complexity of the above solution is O(m + n), where m and n are the total number of elements in the first and second array, respectively.