.png)
Merge Two Sorted Arrays
Problem Statement
Given two sorted arrays, merge them into a single sorted array.
- The resulting array should maintain sorted order.
- Duplicates are allowed unless specified otherwise.
- This is a foundational problem for merging, sorting, and divide & conquer techniques.
Example 1
Input:
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
Output:
[1, 2, 3, 4, 5, 6]
Explanation:
All elements are merged while keeping ascending order.
Example 2
Input:
arr1 = [1, 2, 2, 3]
arr2 = [2, 3, 4]
Output:
[1, 2, 2, 2, 3, 3, 4]
Explanation:
Duplicates are preserved; arrays merged in ascending order.
Why This Problem Is Important
- Tests two-pointer technique and array traversal.
- Frequently used in merge sort, data merging, and interview questions.
- Helps understand efficient in-place merging and time-space trade-offs.
Approaches to Solve the Problem
- Using an Extra Array (Two-Pointer Technique) ✅ Most common and efficient
- Merge Without Extra Space (Advanced, for arrays in same memory)
Approach 1: Using an Extra Array (Two-Pointer Technique)
Idea
- Initialize two pointers i and j at the start of arr1 and arr2.
- Compare elements pointed by i and j.
- Insert the smaller element into the new array and move the respective pointer.
- Continue until one array is exhausted.
- Append remaining elements of the other array.
Time & Space Complexity
- Time Complexity: O(n + m) (where n and m are array sizes)
- Space Complexity: O(n + m)
Algorithm
- Initialize i = 0, j = 0, k = 0 for new array arr3.
- While i < n and j < m:
- If arr1[i] < arr2[j] → arr3[k++] = arr1[i++]
- Else → arr3[k++] = arr2[j++]
- Append remaining elements from arr1 or arr2.
- Return arr3.
C Implementation
#include
int main() {
int arr1[] = {1, 3, 5};
int arr2[] = {2, 4, 6};
int n = 3, m = 3;
int arr3[n + m];
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}
while (i < n) arr3[k++] = arr1[i++];
while (j < m) arr3[k++] = arr2[j++];
for (i = 0; i < n + m; i++)
printf("%d ", arr3[i]);
return 0;
}
C++ Implementation
#include
#include
using namespace std;
int main() {
vector arr1 = {1, 3, 5};
vector arr2 = {2, 4, 6};
vector arr3;
int i = 0, j = 0;
while (i < arr1.size() && j < arr2.size()) {
if (arr1[i] < arr2[j])
arr3.push_back(arr1[i++]);
else
arr3.push_back(arr2[j++]);
}
while (i < arr1.size()) arr3.push_back(arr1[i++]);
while (j < arr2.size()) arr3.push_back(arr2[j++]);
for (int num : arr3)
cout << num << " ";
return 0;
}
Java Implementation
public class Main {
public static void main(String[] args) {
int[] arr1 = {1, 3, 5};
int[] arr2 = {2, 4, 6};
int n = arr1.length, m = arr2.length;
int[] arr3 = new int[n + m];
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}
while (i < n) arr3[k++] = arr1[i++];
while (j < m) arr3[k++] = arr2[j++];
for (int num : arr3)
System.out.print(num + " ");
}
}
Python Implementation
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
arr3 = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
arr3.append(arr1[i])
i += 1
else:
arr3.append(arr2[j])
j += 1
arr3.extend(arr1[i:])
arr3.extend(arr2[j:])
print(arr3)
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr1 = {1, 3, 5};
int[] arr2 = {2, 4, 6};
List arr3 = new List();
int i = 0, j = 0;
while (i < arr1.Length && j < arr2.Length) {
if (arr1[i] < arr2[j])
arr3.Add(arr1[i++]);
else
arr3.Add(arr2[j++]);
}
while (i < arr1.Length) arr3.Add(arr1[i++]);
while (j < arr2.Length) arr3.Add(arr2[j++]);
foreach (int num in arr3)
Console.Write(num + " ");
}
}
JavaScript Implementation
let arr1 = [1, 3, 5];
let arr2 = [2, 4, 6];
let arr3 = [];
let i = 0, j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j])
arr3.push(arr1[i++]);
else
arr3.push(arr2[j++]);
}
while (i < arr1.length) arr3.push(arr1[i++]);
while (j < arr2.length) arr3.push(arr2[j++]);
console.log(arr3);
Approach 2: Merge Without Extra Space (Optional / Advanced)
- If arrays are sorted and adjacent in memory (or one array has enough extra space at the end),
use shifting and insertion to merge in-place. - Time complexity: O(n*m) in naive approach, but can be optimized using gap method.
- Space complexity: O(1).
⚠️ Usually, interviews prefer the two-pointer extra array approach for simplicity.
C Implementation
#include
#include
int nextGap(int gap) {
if (gap <= 1) return 0;
return (gap / 2) + (gap % 2);
}
int main() {
int arr1[] = {1, 3, 5};
int arr2[] = {2, 4, 6};
int n = 3, m = 3;
int gap = n + m;
for (gap = nextGap(gap); gap > 0; gap = nextGap(gap)) {
int i, j;
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap]) {
int t = arr1[i];
arr1[i] = arr1[i + gap];
arr1[i + gap] = t;
}
for (j = gap > n ? gap - n : 0; i < n && j < m; i++, j++)
if (arr1[i] > arr2[j]) {
int t = arr1[i];
arr1[i] = arr2[j];
arr2[j] = t;
}
if (j < m)
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap]) {
int t = arr2[j];
arr2[j] = arr2[j + gap];
arr2[j + gap] = t;
}
}
for (int i = 0; i < n; i++) printf("%d ", arr1[i]);
for (int i = 0; i < m; i++) printf("%d ", arr2[i]);
}
C++ Implementation
#include
#include
using namespace std;
int nextGap(int gap) {
if (gap <= 1) return 0;
return (gap / 2) + (gap % 2);
}
int main() {
vector arr1 = {1, 3, 5};
vector arr2 = {2, 4, 6};
int n = arr1.size(), m = arr2.size();
for (int gap = nextGap(n + m); gap > 0; gap = nextGap(gap)) {
int i, j;
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap])
swap(arr1[i], arr1[i + gap]);
for (j = gap > n ? gap - n : 0; i < n && j < m; i++, j++)
if (arr1[i] > arr2[j])
swap(arr1[i], arr2[j]);
if (j < m)
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap])
swap(arr2[j], arr2[j + gap]);
}
for (int x : arr1) cout << x << " ";
for (int x : arr2) cout << x << " ";
}
Java Implementation
import java.util.*;
public class Main {
static int nextGap(int gap) {
if (gap <= 1) return 0;
return (gap / 2) + (gap % 2);
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 5};
int[] arr2 = {2, 4, 6};
int n = arr1.length, m = arr2.length;
for (int gap = nextGap(n + m); gap > 0; gap = nextGap(gap)) {
int i, j;
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap]) {
int t = arr1[i];
arr1[i] = arr1[i + gap];
arr1[i + gap] = t;
}
for (j = gap > n ? gap - n : 0; i < n && j < m; i++, j++)
if (arr1[i] > arr2[j]) {
int t = arr1[i];
arr1[i] = arr2[j];
arr2[j] = t;
}
if (j < m)
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap]) {
int t = arr2[j];
arr2[j] = arr2[j + gap];
arr2[j + gap] = t;
}
}
for (int x : arr1) System.out.print(x + " ");
for (int x : arr2) System.out.print(x + " ");
}
}
Python Implementation
def next_gap(gap):
if gap <= 1:
return 0
return (gap // 2) + (gap % 2)
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
n, m = len(arr1), len(arr2)
gap = next_gap(n + m)
while gap > 0:
i = 0
while i + gap < n:
if arr1[i] > arr1[i + gap]:
arr1[i], arr1[i + gap] = arr1[i + gap], arr1[i]
i += 1
j = gap - n if gap > n else 0
while i < n and j < m:
if arr1[i] > arr2[j]:
arr1[i], arr2[j] = arr2[j], arr1[i]
i += 1
j += 1
j = 0
while j + gap < m:
if arr2[j] > arr2[j + gap]:
arr2[j], arr2[j + gap] = arr2[j + gap], arr2[j]
j += 1
gap = next_gap(gap)
print(arr1 + arr2)
JavaScript Implementation
function nextGap(gap) {
if (gap <= 1) return 0;
return Math.floor(gap / 2) + (gap % 2);
}
let arr1 = [1, 3, 5];
let arr2 = [2, 4, 6];
let n = arr1.length, m = arr2.length;
for (let gap = nextGap(n + m); gap > 0; gap = nextGap(gap)) {
let i, j;
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap])
[arr1[i], arr1[i + gap]] = [arr1[i + gap], arr1[i]];
for (j = gap > n ? gap - n : 0; i < n && j < m; i++, j++)
if (arr1[i] > arr2[j])
[arr1[i], arr2[j]] = [arr2[j], arr1[i]];
if (j < m)
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap])
[arr2[j], arr2[j + gap]] = [arr2[j + gap], arr2[j]];
}
console.log([...arr1, ...arr2]);
Dry Run (Step-by-Step)
| Step | i | j | arr3 | Notes |
|---|---|---|---|---|
| Initial | 0 | 0 | [] | Start pointers at 0 |
| Compare arr1[0]=1 < arr2[0]=2 | i=1 | j=0 | [1] | Push smaller element |
| Compare arr1[1]=3 > arr2[0]=2 | i=1 | j=1 | [1,2] | Push smaller element |
| Compare arr1[1]=3 < arr2[1]=4 | i=2 | j=1 | [1,2,3] | Continue... |
| Compare arr1[2]=5 > arr2[1]=4 | i=2 | j=2 | [1,2,3,4] | ... |
| Remaining elements | i=2 | j=2 | [1,2,3,4,5,6] | Append remaining elements |
Summary
Merging two sorted arrays is a classic two-pointer problem:
- Two-pointer technique ensures linear time O(n + m).
- Extra array approach is simple and reliable.
- Prepares you for merge sort, interval problems, and advanced array manipulations.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
