Merge two sorted arrays | Techie Delight

Given two integer arrays, each of which is sorted in increasing order, merge them into a single array in increasing order, and return it.

For example,

Input:

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

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

Input:

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

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

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.

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[]

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

{

int k = 0, i = 0, j = 0;

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

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

while (i < X.size() && j < Y.size())

{

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

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

}

else {

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

}

// copy remaining elements

while (i < X.size()) {

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

}

while (j < Y.size()) {

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

}

return aux;

}

int main()

{

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

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 10
Second Array: 2 3 9
After Merge : 1 2 3 4 7 8 9 10

Java

import java.util.Arrays;

class Main

{

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

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

{

int k = 0, i = 0, j = 0;

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

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

while (i < X.length && j < Y.length)

{

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

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

}

else {

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

}

// copy remaining elements

while (i < X.length) {

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

}

while (j < Y.length) {

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

}

return aux;

}

public static void main (String[] args)

{

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

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, 10]
Second Array: [2, 3, 9]
After Merge : [1, 2, 3, 4, 7, 8, 9, 10]

Python

# Function to merge two sorted lists `X` and `Y`

def merge(X, Y):

k = i = j = 0

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

# while there are elements in the first and second arrays

while i < len(X) and j < len(Y):

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 < len(X):

aux[k] = X[i]

k = k + 1

i = i + 1

while j < len(Y):

aux[k] = Y[j]

k = k + 1

j = j + 1

return aux

if __name__ == '__main__':

X = [1, 4, 7, 8, 10]

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, 10]
Second Array: [2, 3, 9]
After Merge : [1, 2, 3, 4, 7, 8, 9, 10]

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.