Merge Two Sorted Arrays in C++

Merge Two Sorted Arrays in C++ (5 Examples).

IntermediateArray Operations ProgramsExample 2 of 7

merge-two-sorted-arrays.cpp

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int main() {
6    int arr1[] = {1, 3, 5, 7};
7    int arr2[] = {2, 4, 6, 8};
8    int n1 = 4, n2 = 4;
9    
10    int merged[n1 + n2];
11    int i = 0, j = 0, k = 0;
12    
13    // Merge while both arrays have elements
14    while (i < n1 && j < n2) {
15        if (arr1[i] < arr2[j]) {
16            merged[k++] = arr1[i++];
17        } else {
18            merged[k++] = arr2[j++];
19        }
20    }
21    
22    // Copy remaining elements
23    while (i < n1) merged[k++] = arr1[i++];
24    while (j < n2) merged[k++] = arr2[j++];
25    
26    cout << "Merged array: ";
27    for (int i = 0; i < n1 + n2; i++) {
28        cout << merged[i] << " ";
29    }
30    cout << endl;
31    
32    return 0;
33}

Output

Merged array: 1 2 3 4 5 6 7 8

What's going on

The program takes two sorted arrays and merges them into one sorted array. For example:

Array 1: [1, 3, 5, 7] (sorted)

Array 2: [2, 4, 6, 8] (sorted)

Merged: [1, 2, 3, 4, 5, 6, 7, 8] (sorted)

The key is that both input arrays are already sorted, which allows efficient merging by comparing elements from both arrays.

Example:

[1, 3, 5] + [2, 4, 6] → [1, 2, 3, 4, 5, 6]

[10, 20] + [15, 25, 30] → [10, 15, 20, 25, 30]

Header Files Used

1.#include <iostream>

Provides cout and cin for input/output operations.

2.#include <algorithm>

Provides merge() algorithm and other STL functions.

Contains useful algorithms for array/container operations.

Declaring Variables

The program declares:

int arr1[] = {1, 3, 5, 7};

int arr2[] = {2, 4, 6, 8};

int n1 = 4, n2 = 4;

arr1 is the first sorted array with 4 elements.

arr2 is the second sorted array with 4 elements.

n1 and n2 store the sizes of the arrays.

Creating the Merged Array

The program creates space for the merged result:

int merged[n1 + n2];

The merged array needs space for all elements from both arrays.

Size = n1 + n2 = 4 + 4 = 8 elements.

The Two-Pointer Merge Algorithm

The core algorithm uses two pointers (indices):

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

i points to current position in arr1.

j points to current position in arr2.

k points to current position in merged array.

Main Merge Loop

while (i < n1 && j < n2) {

if (arr1[i] < arr2[j]) {

merged[k++] = arr1[i++];

} else {

merged[k++] = arr2[j++];

}

How it works step-by-step

(for [1,3,5,7] and [2,4,6,8]):

Initial: i=0, j=0, k=0

Compare arr1[0]=1 with arr2[0]=2

1 < 2, so merged[0]=1, i=1, k=1

Merged: [1, ...]

Step 1: i=1, j=0, k=1

Compare arr1[1]=3 with arr2[0]=2

3 > 2, so merged[1]=2, j=1, k=2

Merged: [1, 2, ...]

Step 2: i=1, j=1, k=2

Compare arr1[1]=3 with arr2[1]=4

3 < 4, so merged[2]=3, i=2, k=3

Merged: [1, 2, 3, ...]

Step 3: i=2, j=1, k=3

Compare arr1[2]=5 with arr2[1]=4

5 > 4, so merged[3]=4, j=2, k=4

Merged: [1, 2, 3, 4, ...]

Step 4: i=2, j=2, k=4

Compare arr1[2]=5 with arr2[2]=6

5 < 6, so merged[4]=5, i=3, k=5

Merged: [1, 2, 3, 4, 5, ...]

Step 5: i=3, j=2, k=5

Compare arr1[3]=7 with arr2[2]=6

7 > 6, so merged[5]=6, j=3, k=6

Merged: [1, 2, 3, 4, 5, 6, ...]

Step 6: i=3, j=3, k=6

Compare arr1[3]=7 with arr2[3]=8

7 < 8, so merged[6]=7, i=4, k=7

Merged: [1, 2, 3, 4, 5, 6, 7, ...]

Loop ends (i >= n1), now copy remaining from arr2.

Copying Remaining Elements

After the main loop, one array may have remaining elements:

while (i < n1) merged[k++] = arr1[i++];

while (j < n2) merged[k++] = arr2[j++];

Why needed?

The main loop stops when one array is exhausted.

The other array may still have elements.

These remaining elements are already sorted, so just copy them.

In our example:

After main loop: i=4 (arr1 exhausted), j=3, k=7

arr2 still has arr2[3]=8

Copy: merged[7]=8, j=4, k=8

Final: [1, 2, 3, 4, 5, 6, 7, 8]

Other Methods (Mentioned but not shown in code)

Method 2: Using merge() Algorithm

int merged[n1 + n2];

merge(arr1, arr1 + n1, arr2, arr2 + n2, merged);

STL merge() function does the merging automatically.

Parameters: start1, end1, start2, end2, output

Simplest method - one line of code.

1#include <algorithm>

Method 3: Using Vectors

vector<int> vec1(arr1, arr1 + n1);

vector<int> vec2(arr2, arr2 + n2);

vector<int> merged;

merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(merged));

Works with vectors instead of arrays.

More flexible and dynamic.

Method 4: Using Priority Queue

priority_queue<int, vector<int>, greater<int>> pq;

1// Add all elements, then extract
2// Less efficient but demonstrates priority queue usage

Method 5: Using Recursion

vector<int> mergeRecursive(vector<int>& arr1, vector<int>& arr2) {

}

Recursive approach - more complex but educational.

1// Recursive merge implementation
2// Base case: one array empty
3// Recursive case: compare and merge

Displaying the Result

The program prints:

for (int i = 0; i < n1 + n2; i++) {

cout << merged[i] << " ";

}

Output:

Merged array: 1 2 3 4 5 6 7 8

The merged array contains all elements in sorted order.

1cout << "Merged array: ";

Understanding the Algorithm

Key Insight

: Since both arrays are sorted, we can merge efficiently by:

1.Comparing the smallest remaining elements from both arrays.

2.Taking the smaller one and moving to the next element in that array.

3.Repeating until one array is exhausted.

4.Copying remaining elements from the other array.

Why it works

Both arrays are sorted, so the smallest unprocessed element in each array is at the current pointer.

By always taking the smaller of the two, we maintain sorted order.

This is the core idea behind merge sort algorithm.

Time and Space Complexity

Time Complexity

: O(n1 + n2)

We process each element exactly once.

Linear time - very efficient.

Space Complexity

: O(n1 + n2)

Need space for the merged array.

Can be done in-place for some cases, but typically needs extra space.

When to Use Each Method

Two Pointers

: Best for learning - shows the algorithm clearly.

merge() Algorithm

: Best for most cases - simple, optimized, recommended.

Vectors

: When working with dynamic data or need vector features.

Priority Queue

: Less efficient - mainly for educational purposes.

Recursion

: Educational - helps understand recursive thinking.

Best Practice

: Use merge() for most applications - it's simple, efficient, and optimized.

Common Use Cases

Merge Sort

Core operation in merge sort algorithm.

Divides array, sorts halves, then merges.

Combining Sorted Data

Merging sorted lists from different sources.

Database operations (merge join).

Combining sorted search results.

Interview Questions

Common coding interview problem.

Tests understanding of two-pointer technique.

Foundation for more complex problems.

Important Considerations

Both Arrays Must Be Sorted

This algorithm only works if both input arrays are sorted.

If not sorted, result will not be sorted.

Sort arrays first if needed.

Equal Elements

When arr1[i] == arr2[j], either can be taken first.

The algorithm takes from arr2 (else branch).

Order of equal elements is preserved within each array.

Different Array Sizes

Algorithm works with arrays of different sizes.

Remaining elements from larger array are copied at the end.

return 0;

This ends the program successfully.

PreviousReverse an Array NextMerge Two Arrays