Arrays are the most basic and essential Data Structures. It is critical to be familiar with the well-known interview problems based on arrays.
In this blog, we will see one of the frequently asked interview problems, i.e., Merge Two Sorted Arrays.
You are provided two non-decreasing sorted arrays, ‘ARR1′ and ‘ARR2.’ Your goal is to merge these two arrays so that the initial sorted elements go into ‘ARR1′ and the rest go into ‘ARR2.’
Given ARR1[ ] = {1, 5, 7, 19, 34} and ARR2[ ] = {2, 4, 8, 8, 12, 17, 19}.
We can see that both of these two arrays are sorted in non-decreasing order. So after merging, we will have:
ARR1[ ] = {1, 2, 4, 5, 7} and ARR2[ ] = {8, 8, 12, 17, 19, 19, 34}.
We can solve this problem in several different ways. Let us first see how we can solve this by using an auxiliary space.
The idea is based on the approach of combining the two arrays and sorting them.
Algorithm:
Let us now see the implementation of the above algorithm.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Creating array, 'ARR3' to store elements of 'ARR1' and 'ARR2'.
vector<int> arr3(m + n);
// Copying elements from 'ARR1' to 'ARR3'.
for (int i = 0; i < m; i++) {
arr3[i] = arr1[i];
}
// Copying elements from 'ARR2' to 'ARR3'.
for (int i = 0; i < n; i++) {
arr3[i + m] = arr2[i];
}
// Sorting 'ARR3'.
sort(arr3.begin(), arr3.end());
// Putting elements back into 'ARR1' from 'ARR3'.
for (int i = 0; i < m; i++) { arr1[i] = arr3[i];
}
// Putting elements back into 'ARR2' from 'ARR3'.
for (int i = m; i < m + n; i++) {
arr2[i - m] = arr3[i];
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}
import java.util.Arrays;
import java.util.Scanner;
public class MergeSortedArrays {
// Function to merge two sorted arrays.
public static void mergeSortedArrays(int[] arr1, int[] arr2) {
int m = arr1.length, n = arr2.length;
int[] arr3 = new int[m + n];
System.arraycopy(arr1, 0, arr3, 0, m);
System.arraycopy(arr2, 0, arr3, m, n);
Arrays.sort(arr3);
System.arraycopy(arr3, 0, arr1, 0, m);
System.arraycopy(arr3, m, arr2, 0, n);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int[] arr1 = new int[m];
for (int i = 0; i < m; i++) {
arr1[i] = scanner.nextInt();
}
int n = scanner.nextInt();
int[] arr2 = new int[n];
for (int i = 0; i < n; i++) {
arr2[i] = scanner.nextInt();
}
mergeSortedArrays(arr1, arr2);
for (int element : arr1) {
System.out.print(element + " ");
}
System.out.println();
for (int element : arr2) {
System.out.print(element + " ");
}
scanner.close();
}
}
def merge_sorted_arrays(arr1, arr2):
m, n = len(arr1), len(arr2)
arr3 = arr1 + arr2
arr3.sort()
return arr3[:m], arr3[m:]
def main():
m = int(input())
arr1 = list(map(int, input().split()))
n = int(input())
arr2 = list(map(int, input().split()))
arr1, arr2 = merge_sorted_arrays(arr1, arr2)
print(' '.join(map(str, arr1)))
print(' '.join(map(str, arr2)))
if __name__ == "__main__":
main()
using System;
using System.Linq;
public class MergeSortedArrays {
// Function to merge two sorted arrays.
public static void MergeSortedArrays(int[] arr1, int[] arr2) {
int m = arr1.Length, n = arr2.Length;
int[] arr3 = new int[m + n];
Array.Copy(arr1, arr3, m);
Array.Copy(arr2, 0, arr3, m, n);
Array.Sort(arr3);
Array.Copy(arr3, arr1, m);
Array.Copy(arr3, m, arr2, 0, n);
}
public static void Main() {
int m = int.Parse(Console.ReadLine());
int[] arr1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
int n = int.Parse(Console.ReadLine());
int[] arr2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
MergeSortedArrays(arr1, arr2);
Console.WriteLine(string.Join(" ", arr1));
Console.WriteLine(string.Join(" ", arr2));
}
}
function mergeSortedArrays(arr1, arr2) {
let m = arr1.length, n = arr2.length;
let arr3 = arr1.concat(arr2);
arr3.sort((a, b) => a - b);
arr1.splice(0, m, ...arr3.slice(0, m));
arr2.splice(0, n, ...arr3.slice(m, m + n));
}
function main() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (m) => {
rl.question('', (arr1) => {
rl.question('', (n) => {
rl.question('', (arr2) => {
arr1 = arr1.split(' ').map(Number);
arr2 = arr2.split(' ').map(Number);
mergeSortedArrays(arr1, arr2);
console.log(arr1.join(' '));
console.log(arr2.join(' '));
rl.close();
});
});
});
});
}
main();
Input
5
1 5 7 19 34
7
2 4 8 8 12 17 19
Output
1 2 4 5 7
8 8 12 17 19 19 34
Time Complexity
O((M + N) * log(M + N)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
Copying elements from ‘ARR1’ to ‘ARR3’ takes O(M) time.
Copying elements from ‘ARR2’ to ‘ARR3’ takes O(N) time.
Sorting of ‘ARR3’ takes O((M + N) * log(M + N)) time.
Putting elements back into ‘ARR1’ from ‘ARR3’ takes O(M) time.
Putting elements back into ‘ARR2’ from ‘ARR3’ takes O(N) time.
So, the overall time complexity is O(M) + O(N) + O((M + N) * log(M + N)) + O(M) + O(N) = O((M + N) * log(M + N)).
Space Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
It is because we have used an additional array, ‘ARR3’ of size ‘M + N’. Hence, the overall space complexity is O(M + N).
Since arrays are already sorted, we can use the merge function of merge sort to optimise the time complexity of Approach 1.
Algorithm:
The implementation of the above algorithm is shown below:
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Creating array, 'ARR3' to store elements of 'ARR1' and 'ARR2'.
vector<int> arr3(m + n);
/*
The variables, 'i', 'j' and 'k' indicates the current index in arrays, 'ARR1', 'ARR2' and 'ARR3', respectively.
*/
int i = 0, j = 0, k = 0;
// Merging arrays, 'ARR1' and 'ARR2' in 'ARR3'.
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
arr3[k] = arr1[i];
i++;
}
else {
arr3[k] = arr2[j];
j++;
}
k++;
}
// Copying remaining elements of 'ARR1' in 'ARR3'.
while (i < m) {
arr3[k] = arr1[i];
k++, i++;
}
// Copying remaining elements of 'ARR2' in 'ARR3'.
while (j < n) {
arr3[k] = arr2[j];
k++, j++;
}
// Putting elements back into 'ARR1' from 'ARR3'.
for (int i = 0; i < m; i++) {
arr1[i] = arr3[i];
}
// Putting elements back into 'ARR2' from 'ARR3'.
for (int i = m; i < m + n; i++) {
arr2[i - m] = arr3[i];
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class MergeSortedArrays {
public static void mergeSortedArrays(List<Integer> arr1, List<Integer> arr2) {
int m = arr1.size(), n = arr2.size();
List<Integer> arr3 = new ArrayList<>(m + n);
int i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (arr1.get(i) < arr2.get(j)) {
arr3.add(arr1.get(i++));
} else {
arr3.add(arr2.get(j++));
}
}
while (i < m) {
arr3.add(arr1.get(i++));
}
while (j < n) {
arr3.add(arr2.get(j++));
}
for (i = 0; i < m; i++) {
arr1.set(i, arr3.get(i));
}
for (i = 0; i < n; i++) {
arr2.set(i, arr3.get(i + m));
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
List<Integer> arr1 = new ArrayList<>();
for (int i = 0; i < m; i++) {
arr1.add(scanner.nextInt());
}
int n = scanner.nextInt();
List<Integer> arr2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr2.add(scanner.nextInt());
}
mergeSortedArrays(arr1, arr2);
for (int num : arr1) {
System.out.print(num + " ");
}
System.out.println();
for (int num : arr2) {
System.out.print(num + " ");
}
scanner.close();
}
}
def merge_sorted_arrays(arr1, arr2):
m, n = len(arr1), len(arr2)
arr3 = []
i = j = 0
while i < m and j < n:
if arr1[i] < arr2[j]:
arr3.append(arr1[i])
i += 1
else:
arr3.append(arr2[j])
j += 1
while i < m:
arr3.append(arr1[i])
i += 1
while j < n:
arr3.append(arr2[j])
j += 1
return arr3[:m], arr3[m:]
def main():
m = int(input())
arr1 = list(map(int, input().split()))
n = int(input())
arr2 = list(map(int, input().split()))
arr1, arr2 = merge_sorted_arrays(arr1, arr2)
print(' '.join(map(str, arr1)))
print(' '.join(map(str, arr2)))
if __name__ == "__main__":
main()
using System;
using System.Linq;
using System.Collections.Generic;
public class MergeSortedArrays {
public static void MergeSortedArrays(List<int> arr1, List<int> arr2) {
int m = arr1.Count, n = arr2.Count;
List<int> arr3 = new List<int>(m + n);
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
arr3.Add(arr1[i++]);
} else {
arr3.Add(arr2[j++]);
}
}
while (i < m) {
arr3.Add(arr1[i++]);
}
while (j < n) {
arr3.Add(arr2[j++]);
}
for (i = 0; i < m; i++) {
arr1[i] = arr3[i];
}
for (i = 0; i < n; i++) {
arr2[i] = arr3[i + m];
}
}
public static void Main() {
int m = int.Parse(Console.ReadLine());
List<int> arr1 = Console.ReadLine().Split().Select(int.Parse).ToList();
int n = int.Parse(Console.ReadLine());
List<int> arr2 = Console.ReadLine().Split().Select(int.Parse).ToList();
MergeSortedArrays(arr1, arr2);
foreach (int num in arr1) {
Console.Write(num + " ");
}
Console.WriteLine();
foreach (int num in arr2) {
Console.Write(num + " ");
}
}
}
function mergeSortedArrays(arr1, arr2) {
let m = arr1.length, n = arr2.length;
let arr3 = [];
let i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
arr3.push(arr1[i++]);
} else {
arr3.push(arr2[j++]);
}
}
while (i < m) {
arr3.push(arr1[i++]);
}
while (j < n) {
arr3.push(arr2[j++]);
}
arr1.splice(0, m, ...arr3.slice(0, m));
arr2.splice(0, n, ...arr3.slice(m, m + n));
}
function main() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (m) => {
rl.question('', (arr1) => {
rl.question('', (n) => {
rl.question('', (arr2) => {
arr1 = arr1.split(' ').map(Number);
arr2 = arr2.split(' ').map(Number);
mergeSortedArrays(arr1, arr2);
console.log(arr1.join(' '));
console.log(arr2.join(' '));
rl.close();
});
});
});
});
}
main();
Input
5
-1 0 7 18 34
7
0 4 8 9 12 12 18
Output
-1 0 0 4 7
8 9 12 12 18 18 34
Time Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
Copying elements of ‘ARR1’ and ‘ARR2’ to ‘ARR3’ takes O(M + N) time.
Putting elements back into ‘ARR1’ from ‘ARR3’ takes O(M) time.
Putting elements back into ‘ARR2’ from ‘ARR3’ takes O(N) time.
So, the overall time complexity is O(M + N) + O(M) + O(N) = O(M + N).
Space Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
Again, the space complexity is O(M + N) as we have used an additional array, ‘ARR3’ of size ‘M + N’.
In this approach, we will compare every element of the array, ‘ARR1’, with the first element of the array, ‘ARR2’. If the element of ‘ARR1’ is greater than the first element of ‘ARR2’, we will swap those elements and sort the array, ‘ARR2’, so that the smallest element is always at the index ‘0’. In this way, we can easily merge the arrays without any extra space.
Algorithm:
Let us now see the implementation of the above algorithm.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Traversing 'ARR1' and comparing its every element with 'ARR2[0]'.
for (int i = 0; i < m; i++) {
// If 'ARR1[i] > ARR2[0]', swap them and sort 'ARR2'.
if (arr1[i] > arr2[0]) {
swap(arr1[i], arr2[0]);
sort(arr2.begin(), arr2.end());
}
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class MergeSortedArrays {
public static void mergeSortedArrays(List<Integer> arr1, List<Integer> arr2) {
int m = arr1.size();
for (int i = 0; i < m; i++) {
if (arr1.get(i) > arr2.get(0)) {
Collections.swap(arr1, i, arr2, 0);
Collections.sort(arr2);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
List<Integer> arr1 = new ArrayList<>();
for (int i = 0; i < m; i++) {
arr1.add(scanner.nextInt());
}
int n = scanner.nextInt();
List<Integer> arr2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr2.add(scanner.nextInt());
}
mergeSortedArrays(arr1, arr2);
for (int num : arr1) {
System.out.print(num + " ");
}
System.out.println();
for (int num : arr2) {
System.out.print(num + " ");
}
scanner.close();
}
}
def merge_sorted_arrays(arr1, arr2):
m = len(arr1)
for i in range(m):
if arr1[i] > arr2[0]:
arr1[i], arr2[0] = arr2[0], arr1[i]
arr2.sort()
def main():
m = int(input())
arr1 = list(map(int, input().split()))
n = int(input())
arr2 = list(map(int, input().split()))
merge_sorted_arrays(arr1, arr2)
print(' '.join(map(str, arr1)))
print(' '.join(map(str, arr2)))
if __name__ == "__main__":
main()
using System;
using System.Linq;
using System.Collections.Generic;
public class MergeSortedArrays {
public static void MergeSortedArrays(List<int> arr1, List<int> arr2) {
int m = arr1.Count;
for (int i = 0; i < m; i++) {
if (arr1[i] > arr2[0]) {
int temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
arr2.Sort();
}
}
}
public static void Main() {
int m = int.Parse(Console.ReadLine());
List<int> arr1 = Console.ReadLine().Split().Select(int.Parse).ToList();
int n = int.Parse(Console.ReadLine());
List<int> arr2 = Console.ReadLine().Split().Select(int.Parse).ToList();
MergeSortedArrays(arr1, arr2);
Console.WriteLine(string.Join(" ", arr1));
Console.WriteLine(string.Join(" ", arr2));
}
}
function mergeSortedArrays(arr1, arr2) {
let m = arr1.length;
for (let i = 0; i < m; i++) {
if (arr1[i] > arr2[0]) {
[arr1[i], arr2[0]] = [arr2[0], arr1[i]];
arr2.sort((a, b) => a - b);
}
}
}
function main() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (m) => {
rl.question('', (arr1) => {
rl.question('', (n) => {
rl.question('', (arr2) => {
arr1 = arr1.split(' ').map(Number);
arr2 = arr2.split(' ').map(Number);
mergeSortedArrays(arr1, arr2);
console.log(arr1.join(' '));
console.log(arr2.join(' '));
rl.close();
});
});
});
});
}
main();
Input
7
1 1 2 7 90 899 1000
2
0 0
Output
0 0 1 1 2 7 90
899 1000
Time Complexity
O(M * N * log(N)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
It is because the for loop runs ‘M’ times, and in each iteration, we are sorting the array, ‘ARR2’, depending on the if condition. In the worst case, when every element of ‘ARR1’ is greater than ‘ARR2’, sorting will be performed in every iteration, taking O(N * log (N)) time.
So, the overall time complexity is O(M) * O(N * log(N)) = O(M * N * log(N)).
Space Complexity
O(1).
As no auxiliary space has been used here.
The only goal in Approach 1 is to place the swapped element in ‘ARR2′ at the correct position after swapping the elements. In such a situation, sorting the entire array is unnecessary. We can use the insertion sort algorithm to shift the elements and place the swapped element at the correct position.
Algorithm:
The implementation of the above algorithms is provided below.
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Traversing 'ARR1' and comparing its every element with 'ARR2[0]'.
for (int i = 0; i < m; i++) {
// If 'ARR1[i] > ARR2[0]', swap them and sort 'ARR2'.
if (arr1[i] > arr2[0]) {
swap(arr1[i], arr2[0]);
int k = arr2[0], j;
// Shifting elements of the array, 'ARR2' to place 'ARR2[0]' at correct position.
for (j = 1; j < n; j++) {
if (arr2[j] < k) {
arr2[j-1] = arr2[j];
}
else {
break;
}
}
arr2[j - 1] = k;
}
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class MergeSortedArrays {
public static void mergeSortedArrays(List<Integer> arr1, List<Integer> arr2) {
int m = arr1.size(), n = arr2.size();
for (int i = 0; i < m; i++) {
if (arr1.get(i) > arr2.get(0)) {
int temp = arr1.get(i);
arr1.set(i, arr2.get(0));
arr2.set(0, temp);
// Insertion sort to find the correct position for the swapped element
int k = arr2.get(0), j;
for (j = 1; j < n && arr2.get(j) < k; j++) {
arr2.set(j - 1, arr2.get(j));
}
arr2.set(j - 1, k);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
List<Integer> arr1 = new ArrayList<>();
for (int i = 0; i < m; i++) {
arr1.add(scanner.nextInt());
}
int n = scanner.nextInt();
List<Integer> arr2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr2.add(scanner.nextInt());
}
mergeSortedArrays(arr1, arr2);
for (int num : arr1) {
System.out.print(num + " ");
}
System.out.println();
for (int num : arr2) {
System.out.print(num + " ");
}
scanner.close();
}
}
def merge_sorted_arrays(arr1, arr2):
m, n = len(arr1), len(arr2)
for i in range(m):
if arr1[i] > arr2[0]:
arr1[i], arr2[0] = arr2[0], arr1[i]
# Insertion sort
k = arr2[0]
j = 1
while j < n and arr2[j] < k:
arr2[j - 1] = arr2[j]
j += 1
arr2[j - 1] = k
def main():
m = int(input())
arr1 = list(map(int, input().split()))
n = int(input())
arr2 = list(map(int, input().split()))
merge_sorted_arrays(arr1, arr2)
print(' '.join(map(str, arr1)))
print(' '.join(map(str, arr2)))
if __name__ == "__main__":
main()
using System;
using System.Linq;
using System.Collections.Generic;
public class MergeSortedArrays {
public static void MergeSortedArrays(List<int> arr1, List<int> arr2) {
int m = arr1.Count, n = arr2.Count;
for (int i = 0; i < m; i++) {
if (arr1[i] > arr2[0]) {
int temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
// Insertion sort
int k = arr2[0], j;
for (j = 1; j < n && arr2[j] < k; j++) {
arr2[j - 1] = arr2[j];
}
arr2[j - 1] = k;
}
}
}
public static void Main() {
int m = int.Parse(Console.ReadLine());
List<int> arr1 = Console.ReadLine().Split().Select(int.Parse).ToList();
int n = int.Parse(Console.ReadLine());
List<int> arr2 = Console.ReadLine().Split().Select(int.Parse).ToList();
MergeSortedArrays(arr1, arr2);
Console.WriteLine(string.Join(" ", arr1));
Console.WriteLine(string.Join(" ", arr2));
}
}
function mergeSortedArrays(arr1, arr2) {
let m = arr1.length, n = arr2.length;
for (let i = 0; i < m; i++) {
if (arr1[i] > arr2[0]) {
[arr1[i], arr2[0]] = [arr2[0], arr1[i]];
// Insertion sort
let k = arr2[0], j = 1;
while (j < n && arr2[j] < k) {
arr2[j - 1] = arr2[j];
j++;
}
arr2[j - 1] = k;
}
}
}
function main() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (m) => {
rl.question('', (arr1) => {
rl.question('', (n) => {
rl.question('', (arr2) => {
arr1 = arr1.split(' ').map(Number);
arr2 = arr2.split(' ').map(Number);
mergeSortedArrays(arr1, arr2);
console.log(arr1.join(' '));
console.log(arr2.join(' '));
rl.close();
});
});
});
});
}
main();
Input
7
1 1 2 7 90 899 1000
2
0 0
Output
0 0 1 1 2 7 90
899 1000
Time Complexity
O(M * N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
It is because the for loop runs ‘M’ times, and in each iteration, we are shifting the elements of the array, ‘ARR2’, depending on the if condition. In the worst case, when all the elements of ‘ARR1’ will be greater than all the elements of ‘ARR2’, shifting will be performed in every iteration for all the elements of ‘ARR2’, which will take O(N) time.
So, the overall time complexity is O(M) * O(N) = O(M * N).
Space Complexity
O(1).
As no auxiliary space has been used here.
Suppose there are ‘M’ elements in ‘ARR1’ and ‘N’ elements in ‘ARR2’. We will modify the arrays, ‘ARR1’ and ‘ARR2’ so that out of these ‘M + N’ elements, the first ‘M’ smaller elements are kept in ‘ARR1’ and the next ‘N’ elements are kept in ‘ARR2’. We will not maintain the sorted order while segregating the elements.
When elements are successfully segregated, we can sort both of these arrays to obtain the desired result.
Algorithm:
The implementation of the above algorithm is provided below:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
int i = 0, j = 0;
// Segregating elements.
while (i < m && j < n) {
if (arr1[i] < arr2[j])
i++;
else {
swap(arr1[m - 1], arr2[j]);
m--, j++;
}
}
// Sorting array, 'ARR1'.
sort(arr1.begin(), arr1.end());
// Sorting array, 'ARR2'.
sort(arr2.begin(), arr2.end());
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}import java.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
public class MergeSortedArrays {
public static void mergeSortedArrays(List<Integer> arr1, List<Integer> arr2) {
int m = arr1.size(), n = arr2.size();
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1.get(i) < arr2.get(j))
i++;
else {
Collections.swap(arr1, m - 1, arr2, j);
m--;
j++;
}
}
Collections.sort(arr1);
Collections.sort(arr2);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
List<Integer> arr1 = new ArrayList<>();
for (int i = 0; i < m; i++) {
arr1.add(scanner.nextInt());
}
int n = scanner.nextInt();
List<Integer> arr2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr2.add(scanner.nextInt());
}
mergeSortedArrays(arr1, arr2);
arr1.forEach(num -> System.out.print(num + " "));
System.out.println();
arr2.forEach(num -> System.out.print(num + " "));
scanner.close();
}
}
def merge_sorted_arrays(arr1, arr2):
m, n = len(arr1), len(arr2)
i, j = 0, 0
while i < m and j < n:
if arr1[i] < arr2[j]:
i += 1
else:
arr1[m - 1], arr2[j] = arr2[j], arr1[m - 1]
m -= 1
j += 1
arr1.sort()
arr2.sort()
def main():
m = int(input())
arr1 = list(map(int, input().split()))
n = int(input())
arr2 = list(map(int, input().split()))
merge_sorted_arrays(arr1, arr2)
print(' '.join(map(str, arr1)))
print(' '.join(map(str, arr2)))
if __name__ == "__main__":
main()
using System;
using System.Linq;
using System.Collections.Generic;
public class MergeSortedArrays {
public static void MergeSortedArrays(List<int> arr1, List<int> arr2) {
int m = arr1.Count, n = arr2.Count;
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
} else {
int temp = arr1[m - 1];
arr1[m - 1] = arr2[j];
arr2[j] = temp;
m--;
j++;
}
}
arr1.Sort();
arr2.Sort();
}
public static void Main() {
int m = int.Parse(Console.ReadLine());
List<int> arr1 = Console.ReadLine().Split().Select(int.Parse).ToList();
int n = int.Parse(Console.ReadLine());
List<int> arr2 = Console.ReadLine().Split().Select(int.Parse).ToList();
MergeSortedArrays(arr1, arr2);
Console.WriteLine(string.Join(" ", arr1));
Console.WriteLine(string.Join(" ", arr2));
}
}
function mergeSortedArrays(arr1, arr2) {
let m = arr1.length, n = arr2.length;
let i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
} else {
[arr1[m - 1], arr2[j]] = [arr2[j], arr1[m - 1]];
m--;
j++;
}
}
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
}
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
readline.question('', m => {
readline.question('', arr1 => {
readline.question('', n => {
readline.question('', arr2 => {
arr1 = arr1.split(' ').map(Number);
arr2 = arr2.split(' ').map(Number);
mergeSortedArrays(arr1, arr2);
console.log(arr1.join(' '));
console.log(arr2.join(' '));
readline.close();
});
});
});
});
Input
4
-3 -1 5 8
7
-2 -1 0 1 3 5 7
Output
-3 -2 -1 -1
0 1 3 5 5 7 8
Time Complexity
O(M * log(M) + N * log(M)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
Segregation of elements of takes O(max(M, N)) time.
Sorting array, ‘ARR1’ takes O(M * log(M)) time.
Sorting array, ‘ARR2’ takes O(N * log(N)) time.
So, the overall time complexity is O(max(M, N)) + O(M * log(M)) + O(N * log(N)) = O(M * log(M) + N * log(M)).
Space Complexity
O(1).
As no auxiliary space has been used here.
In this approach, we will again use the merge function of the merge sort to merge the arrays, ‘ARR1’ and ‘ARR2’. In the usual merge function, we use an auxiliary array to maintain the merged elements in a sorted manner. To achieve the same without any extra space, we will store the new and old values in the same location by using division and modulus operators. Let us see how.
Suppose we have an integer variable, ‘VAR’, containing an integer ‘X’. Now, we also want to store an integer, ‘Y’ in ‘VAR’ so, if we change VAR = X to VAR = X + Y * N, where ‘N’ is an integer greater than both ‘X’ and ‘Y’.
In that case, VAR / N = Y and VAR % N = X.
So, the old value ‘X’ and the new value ‘Y’ are now contained by the same variable ‘VAR’.
The implementation of the above approach is provided below:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// 'MAXN' will store the value greater than all the elements of 'ARR1' and 'ARR2'.
int maxN = max(*max_element(arr1.begin(), arr1.end()), *max_element(arr2.begin(), arr2.end()));
// Incrementing 'MAXN' by 1 to avoid collision in modulo operation.
maxN++;
int i = 0, j = 0, k = 0;
while (i < m && j < n && k < (m + n)) {
// Extracting the old values.
int element1 = arr1[i] % maxN;
int element2 = arr2[j] % maxN;
if (element1 <= element2) {
// Updating element with new value.
if (k < m) {
arr1[k] += (element1 * maxN);
}
else {
arr2[k - m] += (element1 * maxN);
}
i++, k++;
}
else {
// Updating element with new value.
if (k < m) {
arr1[k] += (element2 * maxN);
}
else {
arr2[k - m] += (element2 * maxN);
}
j++, k++;
}
}
// Processing remaining elements of 'ARR1'.
while (i < m) {
int element = arr1[i] % maxN;
if (k < m) {
arr1[k] += (element * maxN);
}
else {
arr2[k - m] += (element * maxN);
}
i++, k++;
}
// Processing remaining elements of 'ARR2'.
while (j < n) {
int element = arr2[j] % maxN;
if (k < m) {
arr1[k] += (element * maxN);
}
else {
arr2[k - m] += (element * maxN);
}
j++, k++;
}
// Updating 'ARR1' elements with new values.
for (int i = 0; i < m; i++) {
arr1[i] = arr1[i] / maxN;
}
// Updating 'ARR2' elements with new values.
for (int i = 0; i < n; i++) {
arr2[i] = arr2[i] / maxN;
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class MergeSortedArrays {
public static void mergeSortedArrays(List<Integer> arr1, List<Integer> arr2) {
int m = arr1.size(), n = arr2.size();
int maxN = Math.max(Collections.max(arr1), Collections.max(arr2)) + 1;
int i = 0, j = 0, k = 0;
while (i < m && j < n && k < (m + n)) {
int element1 = arr1.get(i) % maxN;
int element2 = arr2.get(j) % maxN;
if (element1 <= element2) {
if (k < m) {
arr1.set(k, arr1.get(k) + element1 * maxN);
} else {
arr2.set(k - m, arr2.get(k - m) + element1 * maxN);
}
i++;
} else {
if (k < m) {
arr1.set(k, arr1.get(k) + element2 * maxN);
} else {
arr2.set(k - m, arr2.get(k - m) + element2 * maxN);
}
j++;
}
k++;
}
while (i < m) {
int element = arr1.get(i) % maxN;
if (k < m) {
arr1.set(k, arr1.get(k) + element * maxN);
} else {
arr2.set(k - m, arr2.get(k - m) + element * maxN);
}
i++;
k++;
}
while (j < n) {
int element = arr2.get(j) % maxN;
if (k < m) {
arr1.set(k, arr1.get(k) + element * maxN);
} else {
arr2.set(k - m, arr2.get(k - m) + element * maxN);
}
j++;
k++;
}
for (int idx = 0; idx < m; idx++) {
arr1.set(idx, arr1.get(idx) / maxN);
}
for (int idx = 0; idx < n; idx++) {
arr2.set(idx, arr2.get(idx) / maxN);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
List<Integer> arr1 = new ArrayList<>();
for (int i = 0; i < m; i++) {
arr1.add(scanner.nextInt());
}
int n = scanner.nextInt();
List<Integer> arr2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr2.add(scanner.nextInt());
}
mergeSortedArrays(arr1, arr2);
arr1.forEach(num -> System.out.print(num + " "));
System.out.println();
arr2.forEach(num -> System.out.print(num + " "));
scanner.close();
}
}
def merge_sorted_arrays(arr1, arr2):
m, n = len(arr1), len(arr2)
maxN = max(max(arr1), max(arr2)) + 1
i = j = k = 0
while i < m and j < n and k < (m + n):
element1 = arr1[i] % maxN
element2 = arr2[j] % maxN
if element1 <= element2:
if k < m:
arr1[k] += element1 * maxN
else:
arr2[k - m] += element1 * maxN
i += 1
else:
if k < m:
arr1[k] += element2 * maxN
else:
arr2[k - m] += element2 * maxN
j += 1
k += 1
while i < m:
element = arr1[i] % maxN
if k < m:
arr1[k] += element * maxN
else:
arr2[k - m] += element * maxN
i += 1
k += 1
while j < n:
element = arr2[j] % maxN
if k < m:
arr1[k] += element * maxN
else:
arr2[k - m] += element * maxN
j += 1
k += 1
for idx in range(m):
arr1[idx] //= maxN
for idx in range(n):
arr2[idx] //= maxN
def main():
m = int(input())
arr1 = list(map(int, input().split()))
n = int(input())
arr2 = list(map(int, input().split()))
merge_sorted_arrays(arr1, arr2)
print(' '.join(map(str, arr1)))
print(' '.join(map(str, arr2)))
if __name__ == "__main__":
main()
using System;
using System.Linq;
using System.Collections.Generic;
public class MergeSortedArrays {
public static void MergeSortedArrays(List<int> arr1, List<int> arr2) {
int m = arr1.Count, n = arr2.Count;
int maxN = Math.Max(arr1.Max(), arr2.Max()) + 1;
int i = 0, j = 0, k = 0;
while (i < m && j < n && k < (m + n)) {
int element1 = arr1[i] % maxN;
int element2 = arr2[j] % maxN;
if (element1 <= element2) {
if (k < m) {
arr1[k] += element1 * maxN;
} else {
arr2[k - m] += element1 * maxN;
}
i++;
} else {
if (k < m) {
arr1[k] += element2 * maxN;
} else {
arr2[k - m] += element2 * maxN;
}
j++;
}
k++;
}
while (i < m) {
int element = arr1[i] % maxN;
if (k < m) {
arr1[k] += element * maxN;
} else {
arr2[k - m] += element * maxN;
}
i++;
k++;
}
while (j < n) {
int element = arr2[j] % maxN;
if (k < m) {
arr1[k] += element * maxN;
} else {
arr2[k - m] += element * maxN;
}
j++;
k++;
}
for (int idx = 0; idx < m; idx++) {
arr1[idx] /= maxN;
}
for (int idx = 0; idx < n; idx++) {
arr2[idx] /= maxN;
}
}
public static void Main() {
int m = int.Parse(Console.ReadLine());
List<int> arr1 = Console.ReadLine().Split().Select(int.Parse).ToList();
int n = int.Parse(Console.ReadLine());
List<int> arr2 = Console.ReadLine().Split().Select(int.Parse).ToList();
MergeSortedArrays(arr1, arr2);
Console.WriteLine(string.Join(" ", arr1));
Console.WriteLine(string.Join(" ", arr2));
}
}
function mergeSortedArrays(arr1, arr2) {
const m = arr1.length, n = arr2.length;
const maxN = Math.max(Math.max(...arr1), Math.max(...arr2)) + 1;
let i = 0, j = 0, k = 0;
while (i < m && j < n && k < (m + n)) {
const element1 = arr1[i] % maxN;
const element2 = arr2[j] % maxN;
if (element1 <= element2) {
if (k < m) {
arr1[k] += element1 * maxN;
} else {
arr2[k - m] += element1 * maxN;
}
i++;
} else {
if (k < m) {
arr1[k] += element2 * maxN;
} else {
arr2[k - m] += element2 * maxN;
}
j++;
}
k++;
}
while (i < m) {
const element = arr1[i] % maxN;
if (k < m) {
arr1[k] += element * maxN;
} else {
arr2[k - m] += element * maxN;
}
i++;
k++;
}
while (j < n) {
const element = arr2[j] % maxN;
if (k < m) {
arr1[k] += element * maxN;
} else {
arr2[k - m] += element * maxN;
}
j++;
k++;
}
for (let idx = 0; idx < m; idx++) {
arr1[idx] = Math.floor(arr1[idx] / maxN);
}
for (let idx = 0; idx < n; idx++) {
arr2[idx] = Math.floor(arr2[idx] / maxN);
}
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('Number of elements in arr1: ', m => {
rl.question('Elements of arr1: ', arr1 => {
rl.question('Number of elements in arr2: ', n => {
rl.question('Elements of arr2: ', arr2 => {
arr1 = arr1.split(' ').map(Number);
arr2 = arr2.split(' ').map(Number);
mergeSortedArrays(arr1, arr2);
console.log(arr1.join(' '));
console.log(arr2.join(' '));
rl.close();
});
});
});
});
Input
4
1 3 5 8
7
0 1 3 5 7 8 11
Output
0 1 1 3
3 5 5 7 8 8 11
Time Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
Merging elements of ‘ARR1’ and ‘ARR2’ in ‘ARR3’ takes O(M + N) time.
Updating ‘ARR1’ elements with new values takes O(M) time.
Updating ‘ARR2’ elements with new values takes O(N) time.
So, the overall time complexity is O(M + N) + O(M) + O(N) = O(M + N).
Space Complexity
O(1).
As no auxiliary space has been used here.
Merging a sorted array refers to the process of combining two or more sorted arrays into a single sorted array, maintaining the order of elements. This operation is common in algorithms and data structures for tasks like merging data from multiple sources or combining sorted lists.
To merge two arrays into a single sorted array, initialize a new array, and then iterate through both input arrays simultaneously, comparing elements and adding the smaller one to the new array. Continue until both input arrays are fully processed.
To merge two sorted arrays in C, create a new array with sufficient space, then iterate through both arrays, comparing elements, and copying the smaller one into the new array. Continue until both input arrays are fully processed, resulting in a merged sorted array.
Merge two sorted arrays using two pointers in C by initializing two pointers for each array, comparing elements at those pointers, and copying the smaller one into a new array. Move the respective pointer forward and repeat until both arrays are fully merged.
With this discussion, this blog attempted to break down the famous interview problem, merge two sorted arrays. We discussed different approaches and their time and space complexity. Now, next time someone asks you to merge two sorted arrays without extra space, you are going to shine!
Recommended problems -
Also Read -
8+ registered 
1130+ registered 392+ registered 8+ registered 1130+ registered 