Merge Two Sorted Arrays: C, C++, Java and Python

Merging two sorted arrays into a single sorted array appears in placement coding rounds at service-tier companies including Wipro, Cognizant, and Capgemini.

The problem is compact enough to fit in a 20-minute coding slot, but it reveals three things at once: whether you write a correct traversal loop, whether you state time complexity without being prompted, and whether you know a second approach when the interviewer asks for one. Three methods cover every variant a placement test can raise.

The Problem

Given two sorted arrays, produce a single sorted array containing all elements from both.

• Input: arr1 = [1, 3, 5, 7], arr2 = [2, 4, 6, 8]
• Expected output: [1, 2, 3, 4, 5, 6, 7, 8]

Three edge cases worth working through before writing code:

• Duplicates: arr1 = [1, 3, 3], arr2 = [2, 3, 5] gives [1, 2, 3, 3, 3, 5]. Duplicates are preserved as-is.
• Empty array: arr1 = [], arr2 = [4, 7] gives [4, 7]. Any correct implementation must handle this without a null-pointer or index error.
• One array much longer: arr1 = [1, 2], arr2 = [3, 4, 5, 6, 7] gives [1, 2, 3, 4, 5, 6, 7]. The tail-copy step after the main loop handles this case.

The problem appears across the 20 most-asked data structures interview questions in placement rounds, often as a stepping stone before two-pointer problems on linked lists or strings.

Approach 1: Two-Pointer Linear Merge

Two indices walk the two arrays simultaneously. At each step, the smaller of the two current elements moves into the result array. When one array is exhausted, the remaining elements of the other are copied directly.

Algorithm

• Initialise i = 0, j = 0, k = 0.
• While i < m and j < n: if arr1[i] <= arr2[j], place arr1[i] at result[k] and advance i and k; otherwise place arr2[j] and advance j and k.
• Copy any remaining elements from arr1 (when i < m).
• Copy any remaining elements from arr2 (when j < n).

C

#include <stdio.h>

void mergeSorted(int arr1[], int m, int arr2[], int n, int result[]) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (arr1[i] <= arr2[j])
            result[k++] = arr1[i++];
        else
            result[k++] = arr2[j++];
    }
    while (i < m) result[k++] = arr1[i++];
    while (j < n) result[k++] = arr2[j++];
}

int main() {
    int a[] = {1, 3, 5, 7};
    int b[] = {2, 4, 6, 8};
    int merged[8];
    mergeSorted(a, 4, b, 4, merged);
    for (int i = 0; i < 8; i++)
        printf("%d ", merged[i]);
    return 0;
}

C++

C++ can express the same logic manually or through std::merge from the standard library, which runs in exactly O(m+n) comparisons and writes to any output iterator.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {1, 3, 5, 7};
    vector<int> b = {2, 4, 6, 8};
    vector<int> result(8);
    merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());
    for (int x : result) cout << x << " ";
    return 0;
}

Java

import java.util.Arrays;

public class MergeSorted {
    static int[] merge(int[] a, int[] b) {
        int m = a.length, n = b.length;
        int[] result = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n)
            result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
        while (i < m) result[k++] = a[i++];
        while (j < n) result[k++] = b[j++];
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(merge(
            new int[]{1, 3, 5, 7}, new int[]{2, 4, 6, 8}
        )));
    }
}

Python

def merge_sorted(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

print(merge_sorted([1, 3, 5, 7], [2, 4, 6, 8]))
# Output: [1, 2, 3, 4, 5, 6, 7, 8]

Complexity

• Time: O(m+n). Each of the m+n elements is visited and written exactly once.
• Space: O(m+n) for the result array. No additional data structures.

This is the approach to open with in any placement test. It needs no library headers, it’s transparent to trace on a whiteboard, and it is the correct answer to “what is the optimal approach?”

Approach 2: Concatenate and Sort

Copy both arrays into a single array, then sort it. The algorithm is two lines. The trade-off is time: sorting ignores the fact that the inputs are already sorted, so it does more work than necessary.

Algorithm

• Copy arr1 and arr2 into a combined array of size m+n.
• Sort the combined array using any comparison sort.

C

#include <stdio.h>
#include <stdlib.h>

int compare(const void *x, const void *y) {
    return (*(int *)x - *(int *)y);
}

void mergeConcat(int arr1[], int m, int arr2[], int n, int result[]) {
    for (int i = 0; i < m; i++) result[i] = arr1[i];
    for (int i = 0; i < n; i++) result[m + i] = arr2[i];
    qsort(result, m + n, sizeof(int), compare);
}

int main() {
    int a[] = {1, 3, 5, 7};
    int b[] = {2, 4, 6, 8};
    int merged[8];
    mergeConcat(a, 4, b, 4, merged);
    for (int i = 0; i < 8; i++)
        printf("%d ", merged[i]);
    return 0;
}

Python

def merge_concat_sort(a, b):
    return sorted(a + b)

print(merge_concat_sort([1, 3, 5, 7], [2, 4, 6, 8]))
# Output: [1, 2, 3, 4, 5, 6, 7, 8]

Complexity

• Time: O((m+n) log(m+n)). Concatenation is O(m+n); the sort dominates.
• Space: O(m+n) for the combined array.

When an interviewer accepts this answer, it usually means they are checking baseline competence, not algorithm design. It is worth mentioning this approach and its complexity, then pivoting to the two-pointer approach and explaining why it is faster.

Approach 3: Min-Heap Merge

A min-heap holds the current front element from each array. The smallest element across all fronts is always at the heap root. Pop it, write it to the result, push the next element from the same array. Repeat until all elements are processed.

For two arrays the heap contains at most 2 elements at any time. This makes each push and pop O(log 2) = O(1). The real advantage is generalisability: the same code handles k sorted arrays by starting with k elements in the heap and running the same pop-push loop.

Python

Python’s heapq.merge implements this directly as a lazy iterator. For two arrays:

import heapq

def merge_heap(a, b):
    return list(heapq.merge(a, b))

print(merge_heap([1, 3, 5, 7], [2, 4, 6, 8]))
# Output: [1, 2, 3, 4, 5, 6, 7, 8]

For the explicit k-way implementation that makes the heap structure visible:

import heapq

def merge_heap_explicit(a, b):
    result = []
    heap = []
    arrays = [a, b]
    for arr_id, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], arr_id, 0))
    while heap:
        val, arr_id, elem_idx = heapq.heappop(heap)
        result.append(val)
        next_idx = elem_idx + 1
        if next_idx < len(arrays[arr_id]):
            heapq.heappush(heap, (arrays[arr_id][next_idx], arr_id, next_idx))
    return result

print(merge_heap_explicit([1, 3, 5, 7], [2, 4, 6, 8]))
# Output: [1, 2, 3, 4, 5, 6, 7, 8]

Java

import java.util.*;

public class MergeHeap {
    static int[] merge(int[] a, int[] b) {
        // Each entry: [value, array_id, element_index]
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[0] - y[0]);
        if (a.length > 0) pq.offer(new int[]{a[0], 0, 0});
        if (b.length > 0) pq.offer(new int[]{b[0], 1, 0});
        int[][] arrays = {a, b};
        int[] result = new int[a.length + b.length];
        int k = 0;
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            result[k++] = curr[0];
            int next = curr[2] + 1;
            if (next < arrays[curr[1]].length)
                pq.offer(new int[]{arrays[curr[1]][next], curr[1], next});
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(merge(
            new int[]{1, 3, 5, 7}, new int[]{2, 4, 6, 8}
        )));
    }
}

Complexity

• Time: O((m+n) log k) where k is the number of input arrays. For k=2, log 2 = 1, so O(m+n). For k arrays of equal size n, O(kn log k).
• Space: O(m+n) for the output, plus O(k) for the heap.

The heap approach is worth knowing for follow-up questions: “what if there are k=10 sorted arrays?” Two-pointer cannot extend to k arrays without nesting; the heap approach scales cleanly.

Comparing the Three Approaches

Approach	Time	Extra Space	Best used when
Two-pointer	O(m+n)	O(1) beyond output	Default answer; exploit sorted property
Concatenate and sort	O((m+n) log(m+n))	O(1) beyond output	Simplest code; order does not matter
Min-heap (k=2)	O(m+n)	O(k) heap	Generalising to k sorted arrays

The practical decision in a placement interview is straightforward: open with the two-pointer. State O(m+n) time and O(m+n) space before the interviewer asks. If asked “can you do it differently?” introduce the concatenate-and-sort approach and explain the time trade-off. If asked “what if there were ten arrays?” describe the heap approach and its O(kn log k) complexity.

For a related array-traversal problem that has the same three-tier structure (fast linear approach, library shortcut, complex generalisation), see finding the smallest and largest element in an array.

The min-heap pattern that handles k=2 sorted arrays here is the same structure that merges k parallel ranked streams in production retrieval systems, where multiple document indexes contribute sorted candidate lists. TinkerLLM is the ₹299 entry point for building those retrieval pipelines and observing how the same merge logic operates on real LLM outputs.