Java Program to Merge Two Sorted Arrays

To merge two sorted arrays in Java, create a new array and use two pointers to compare elements from both arrays, adding the smaller element to the new array with code like while(i < arr1.length && j < arr2.length) { if(arr1[i] <= arr2[j]) merged[k++] = arr1[i++]; else merged[k++] = arr2[j++]; }.

Examples

Inputarr1 = {1, 3, 5}, arr2 = {2, 4, 6}

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

Inputarr1 = {0, 2, 4}, arr2 = {1, 3, 5, 7}

Output[0, 1, 2, 3, 4, 5, 7]

Inputarr1 = {}, arr2 = {1, 2, 3}

Output[1, 2, 3]

How to Think About It

To merge two sorted arrays, think of walking through both arrays at the same time. Compare the current elements from each array and pick the smaller one to add to the new array. Move forward in the array from which you took the element. Repeat until all elements from both arrays are added.

Algorithm

1

Create a new array to hold the merged result with size equal to sum of both arrays' lengths.

2

Initialize three pointers: one for each input array and one for the merged array.

3

Compare elements at the pointers of both arrays; add the smaller element to the merged array and move that pointer forward.

4

If one array is exhausted, add all remaining elements from the other array to the merged array.

5

Return or print the merged array.

Code

java

public class MergeSortedArrays {
    public static int[] merge(int[] arr1, int[] arr2) {
        int[] merged = new int[arr1.length + arr2.length];
        int i = 0, j = 0, k = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] <= arr2[j]) {
                merged[k++] = arr1[i++];
            } else {
                merged[k++] = arr2[j++];
            }
        }
        while (i < arr1.length) merged[k++] = arr1[i++];
        while (j < arr2.length) merged[k++] = arr2[j++];
        return merged;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5};
        int[] arr2 = {2, 4, 6};
        int[] result = merge(arr1, arr2);
        System.out.print("[");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

Output

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

Dry Run

Let's trace merging arr1 = {1, 3, 5} and arr2 = {2, 4, 6} through the code

1

Initialize pointers and merged array

i=0, j=0, k=0, merged=[_, _, _, _, _, _]

2

Compare arr1[i]=1 and arr2[j]=2

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

3

Compare arr1[i]=3 and arr2[j]=2

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

4

Compare arr1[i]=3 and arr2[j]=4

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

5

Compare arr1[i]=5 and arr2[j]=4

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

6

Compare arr1[i]=5 and arr2[j]=6

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

7

arr1 exhausted, add remaining arr2[j]=6

merged[5]=6; j=3, k=6

i	j	k	merged array
0	0	0	[_, _, _, _, _, _]
1	0	1	[1, _, _, _, _, _]
1	1	2	[1, 2, _, _, _, _]
2	1	3	[1, 2, 3, _, _, _]
2	2	4	[1, 2, 3, 4, _, _]
3	2	5	[1, 2, 3, 4, 5, _]
3	3	6	[1, 2, 3, 4, 5, 6]

Why This Works

Step 1: Two pointers track positions

We use pointers i and j to track current elements in each array, so we can compare them easily.

Step 2: Compare and pick smaller element

At each step, we compare arr1[i] and arr2[j] and add the smaller one to the merged array to keep it sorted.

Step 3: Add leftovers after one array ends

When one array finishes, we add all remaining elements from the other array because they are already sorted.

Alternative Approaches

Using ArrayList and Collections.sort

java

import java.util.*;
public class MergeSortedArraysAlt {
    public static int[] merge(int[] arr1, int[] arr2) {
        List<Integer> list = new ArrayList<>();
        for (int n : arr1) list.add(n);
        for (int n : arr2) list.add(n);
        Collections.sort(list);
        return list.stream().mapToInt(i -> i).toArray();
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5};
        int[] arr2 = {2, 4, 6};
        int[] result = merge(arr1, arr2);
        System.out.println(java.util.Arrays.toString(result));
    }
}

Simpler code but less efficient because it sorts the combined array instead of merging sorted arrays directly.

Using Java 8 Streams

java

import java.util.stream.*;
public class MergeSortedArraysStream {
    public static int[] merge(int[] arr1, int[] arr2) {
        return IntStream.concat(IntStream.of(arr1), IntStream.of(arr2))
                        .sorted()
                        .toArray();
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5};
        int[] arr2 = {2, 4, 6};
        int[] result = merge(arr1, arr2);
        System.out.println(java.util.Arrays.toString(result));
    }
}

Very concise but also sorts the combined array, which is less efficient than merging sorted arrays.

Complexity: O(n + m) time, O(n + m) space

Time Complexity

The program loops through both arrays once, so it takes time proportional to the sum of their lengths, O(n + m).

Space Complexity

A new array is created to hold all elements, so space used is also proportional to the total number of elements, O(n + m).

Which Approach is Fastest?

The two-pointer merge is fastest because it avoids sorting the combined array, unlike alternatives that sort after combining.

Approach	Time	Space	Best For
Two-pointer merge	O(n + m)	O(n + m)	Merging already sorted arrays efficiently
Combine and sort (ArrayList)	O((n + m) log(n + m))	O(n + m)	Simple code, less efficient
Streams with sort	O((n + m) log(n + m))	O(n + m)	Concise code, less efficient