Java Program to Merge Two Sorted Arrays (With Examples)

In this tutorial, I will demonstrate how to merge two sorted arrays into a single sorted array in Java. This is a common array-based coding interview question that helps you understand array traversal, comparison operations, and the two-pointer technique.

Suppose you have two integer arrays sorted in ascending order. Your task is to combine their elements into one array while maintaining the sorted order.

A straightforward solution is to combine the arrays and sort the result. However, because both input arrays are already sorted, you can solve the problem more efficiently using two pointers.

In this tutorial, you will learn two approaches with complete Java programs, example outputs, a step-by-step dry run, time complexity analysis, and important edge cases.

1. Problem Statement

Write a Java program to merge two sorted integer arrays into one sorted array.

Example:

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

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

Explanation: Both input arrays are sorted in ascending order. After merging them, the resulting array contains every element from both arrays, also in ascending order.

Another Example with Duplicate Elements

Input:
arr1 = [1, 2, 2, 5]
arr2 = [2, 3, 5, 6]

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

Notice that duplicate values are preserved. The goal is to merge the arrays, not remove duplicates.

2. Method 1: Merge Two Sorted Arrays Using Two Pointers

The two-pointer technique is the most efficient approach for merging two already sorted arrays.

Instead of sorting the combined elements again, this method compares the current elements of both arrays and places the smaller element into the resulting array.

How the Two-Pointer Technique Works

Create a new array with enough space to store elements from both input arrays.
Initialize three pointers: i for the first array, j for the second array, and k for the merged array.
Compare the elements at positions i and j.
Copy the smaller element into the merged array and advance its corresponding pointer.
Continue until one input array has been completely processed.
Copy any remaining elements from the other array into the merged array.

Java Program Using Two Pointers

import java.util.Arrays;

public class MergeSortedArrays {

    public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {

        int n = arr1.length;
        int m = arr2.length;

        int[] merged = new int[n + m];

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

        // Compare and merge elements from both arrays
        while (i < n && j < m) {

            if (arr1[i] <= arr2[j]) {
                merged[k] = arr1[i];
                i++;
            } else {
                merged[k] = arr2[j];
                j++;
            }

            k++;
        }

        // Copy remaining elements from the first array
        while (i < n) {
            merged[k] = arr1[i];
            i++;
            k++;
        }

        // Copy remaining elements from the second array
        while (j < m) {
            merged[k] = arr2[j];
            j++;
            k++;
        }

        return merged;
    }

    public static void main(String[] args) {

        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};

        int[] result = mergeSortedArrays(arr1, arr2);

        System.out.println("First Array: "
                + Arrays.toString(arr1));

        System.out.println("Second Array: "
                + Arrays.toString(arr2));

        System.out.println("Merged Sorted Array: "
                + Arrays.toString(result));
    }
}

Output

First Array: [1, 3, 5, 7]
Second Array: [2, 4, 6, 8]
Merged Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8]

3. Step-by-Step Explanation

Let's understand the important parts of the program.

Step 1: Create the Merged Array

int n = arr1.length;
int m = arr2.length;

int[] merged = new int[n + m];

The merged array must hold all elements from both arrays.

If the first array contains four elements and the second array also contains four elements, the merged array requires eight positions.

Step 2: Initialize Three Pointers

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

i tracks the current element in the first array.
j tracks the current element in the second array.
k tracks the next available position in the merged array.

Initially, all three pointers start at index zero.

Step 3: Compare Elements and Merge

while (i < n && j < m) {

    if (arr1[i] <= arr2[j]) {
        merged[k] = arr1[i];
        i++;
    } else {
        merged[k] = arr2[j];
        j++;
    }

    k++;
}

The loop continues as long as both arrays have unprocessed elements.

If the current element from the first array is smaller than or equal to the current element from the second array, the program copies that element into the merged array.

Otherwise, it copies the element from the second array.

After each comparison, the appropriate input pointer and the merged-array pointer advance.

Using <= also means that when values are equal, the program takes the element from the first array before the matching element from the second array.

Step 4: Copy Remaining Elements

Once one array is exhausted, the other array may still contain elements.

while (i < n) {
    merged[k] = arr1[i];
    i++;
    k++;
}

while (j < m) {
    merged[k] = arr2[j];
    j++;
    k++;
}

Because both arrays were already sorted, the remaining elements can be copied directly without further comparisons.

4. Dry Run of the Two-Pointer Algorithm

Consider these arrays:

arr1 = [1, 3, 5]
arr2 = [2, 4, 6]

The algorithm compares the current elements and appends the smaller one to the result.

Step	Comparison	Selected Element	Merged Array So Far
1	1 vs 2	1	[1]
2	3 vs 2	2	[1, 2]
3	3 vs 4	3	[1, 2, 3]
4	5 vs 4	4	[1, 2, 3, 4]
5	5 vs 6	5	[1, 2, 3, 4, 5]
6	Copy remaining 6	6	[1, 2, 3, 4, 5, 6]

Final result:

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

The algorithm visits every element only once and produces a sorted array without calling a sorting method.

5. Method 2: Merge Arrays Using System.arraycopy() and Arrays.sort()

Another way to solve this problem is to copy both arrays into a new array and then sort the combined array.

This approach is straightforward and useful when you want a short solution. It also works when the original arrays are not sorted.

However, sorting the combined array performs unnecessary work when both input arrays are already sorted.

Java Program Using Arrays.sort()

import java.util.Arrays;

public class MergeArraysUsingSort {

    public static int[] mergeArrays(int[] arr1, int[] arr2) {

        int[] merged = new int[arr1.length + arr2.length];

        // Copy the first array
        System.arraycopy(
                arr1, 0, merged, 0, arr1.length);

        // Copy the second array
        System.arraycopy(
                arr2, 0, merged, arr1.length, arr2.length);

        // Sort the combined array
        Arrays.sort(merged);

        return merged;
    }

    public static void main(String[] args) {

        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};

        int[] result = mergeArrays(arr1, arr2);

        System.out.println("Merged Sorted Array: "
                + Arrays.toString(result));
    }
}

Output

Merged Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8]

How This Approach Works

Create a new array that can store all elements from both arrays.
Use System.arraycopy() to copy the first array into the beginning of the new array.
Copy the second array immediately after the first array's elements.
Call Arrays.sort() to sort the combined array.
Return the resulting sorted array.

The System.arraycopy() method efficiently copies elements between arrays. The Arrays.sort() method sorts the combined integer array in ascending order.

6. Time and Space Complexity

Let's compare the two methods.

Approach	Time Complexity	Output Space	Recommendation
Two pointers	O(n + m)	O(n + m)	Best for sorted input arrays
Copy and sort	O((n + m) log(n + m)) worst case	O(n + m)	Simple alternative

Here, n represents the length of the first array, and m represents the length of the second array.

Why Is the Two-Pointer Approach Faster?

The two-pointer approach takes advantage of the fact that both arrays are already sorted.

Each element is processed once, so the total running time is proportional to the combined length of the arrays.

The copy-and-sort approach first combines the arrays and then sorts them. Sorting introduces additional work and has a worst-case time complexity of O((n + m) log(n + m)) for Java's primitive integer arrays.

For coding interviews, the two-pointer approach is generally the preferred solution.

7. Handling Edge Cases

A reliable solution should also work with empty arrays, duplicate values, negative numbers, and arrays of different lengths.

Case 1: First Array Is Empty

Input:
arr1 = []
arr2 = [1, 2, 3]

Output:
[1, 2, 3]

The two-pointer algorithm copies every element from the second array.

Case 2: Second Array Is Empty

Input:
arr1 = [4, 5, 6]
arr2 = []

Output:
[4, 5, 6]

Case 3: Both Arrays Are Empty

Input:
arr1 = []
arr2 = []

Output:
[]

Case 4: Arrays Contain Duplicate Elements

Input:
arr1 = [1, 2, 2, 4]
arr2 = [2, 3, 4, 4]

Output:
[1, 2, 2, 2, 3, 4, 4, 4]

All duplicate values remain in the merged array.

Case 5: Arrays Contain Negative Numbers

Input:
arr1 = [-10, -5, 0]
arr2 = [-8, -2, 3]

Output:
[-10, -8, -5, -2, 0, 3]

The same comparison logic works for negative integers.

Case 6: Arrays Have Different Lengths

Input:
arr1 = [1, 5]
arr2 = [2, 3, 4, 6, 7]

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

The algorithm handles arrays of different lengths without requiring additional changes.

8. Common Mistakes to Avoid

Mistake 1: Forgetting Remaining Elements

A common mistake is stopping as soon as one array is exhausted.

For example:

arr1 = [1, 2]
arr2 = [3, 4, 5]

After the first array is exhausted, the remaining values from the second array must still be copied into the result.

Mistake 2: Incrementing the Wrong Pointer

If the program copies an element from the first array, it must increment i.

If it copies an element from the second array, it must increment j.

Incrementing the wrong pointer can skip elements or produce incorrect results.

Mistake 3: Assuming Unsorted Arrays Will Work

The two-pointer algorithm requires both input arrays to be sorted in ascending order.

For unsorted arrays, sort both inputs first or use the copy-and-sort approach.

Mistake 4: Using an Incorrect Result Array Size

The merged array must have a length equal to the sum of the input array lengths.

int[] merged = new int[arr1.length + arr2.length];

An array that is too small will cause an ArrayIndexOutOfBoundsException when the program attempts to insert more elements than it can hold.

9. Frequently Asked Questions

Q1. What is the best way to merge two sorted arrays in Java?

The two-pointer technique is generally the best approach. It merges both arrays in O(n + m) time without sorting the elements again.

Q2. Can I merge two sorted arrays without using Arrays.sort()?

Yes. The two-pointer technique merges two sorted arrays without calling Arrays.sort().

Q3. Does the two-pointer technique remove duplicates?

No. It preserves every element, including duplicate values. Removing duplicates requires additional logic.

Q4. Does the algorithm modify the original arrays?

No. Both examples create a new array to hold the merged result. The original arrays remain unchanged.

Q5. Can I merge two sorted arrays in place?

Yes, but the implementation depends on the problem's constraints. If the first array has enough extra capacity to hold all elements from the second array, you can merge them from right to left using three pointers without creating another result array.

Q6. Does the two-pointer approach work with descending arrays?

Yes, but you must adjust the comparison. For arrays sorted in descending order, select the larger current element first.

Q7. What happens if an input array is null?

The examples assume both input arrays are non-null. Passing null causes a NullPointerException when the program accesses the array's length. If null inputs are possible in your application, add explicit validation or define how null should be handled.

10. Conclusion

In this tutorial, you learned how to merge two sorted arrays into one sorted array in Java using two different methods.

Two-pointer technique: Merges sorted arrays efficiently in O(n + m) time.
System.arraycopy() with Arrays.sort(): Combines both arrays and sorts the result using Java's built-in methods.

For Java coding interviews, I recommend practicing the two-pointer technique. It takes advantage of the sorted input, avoids unnecessary sorting, and demonstrates an important algorithmic pattern.

The same concept appears in merge sort, linked-list merging, and many other array-based interview problems.

11. Official Java Documentation

For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:

Java Arrays Class — Documentation for Arrays.sort() and Arrays.toString().
Java System Class — Documentation for System.arraycopy().
Java Language Specification: Arrays — Details about arrays in the Java programming language.

Take Your Programming Skills to the Next Level!

🎓 Udemy Personal Plan

💼 Udemy Business