Merge Sorted Arrays in Java: Solution, Explanation & Practice

Merge two sorted arrays into one sorted array

Problem summary

Write a program that merges two sorted arrays into a single sorted array.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8}; // Test case 1
        
        // Merge into sorted result
        // Print space-separated
    }
}

Expected output and test cases

Merge two arrays
```
1 2 3 4 5 6 7 8
```
Merge [1,3,5] and [2,4]
```
1 2 3 4 5
```
Merge with duplicates
```
1 1 2 2 3 3
```

Hints

Use two pointers, one for each array
Compare and pick smaller element
Don't forget remaining elements

Validated solution

Reveal Java solution

public class Main {
    static int[] merge(int[] first, int[] second) {
        int[] merged = new int[first.length + second.length];
        int i = 0, j = 0, write = 0;
        while (i < first.length && j < second.length) {
            merged[write++] = first[i] <= second[j] ? first[i++] : second[j++];
        }
        while (i < first.length) merged[write++] = first[i++];
        while (j < second.length) merged[write++] = second[j++];
        return merged;
    }
    public static void main(String[] args) {
        int[] values = merge(new int[] {1, 3, 5, 7}, new int[] {2, 4, 6, 8});
        for (int value : values) System.out.print(value + " ");
    }
}

How to approach the problem

Two read pointers expose the smallest unmerged value from each sorted input. Write the smaller choice, then copy whichever tail remains after one input is exhausted.

Approach

Allocate exactly the combined output length.
Compare the current heads while both inputs remain.
Copy the untouched tail after the comparison loop.

Time and space complexity

Time: O(n + m). Space: O(n + m).

Edge cases to test

Either input may be empty.
Using <= keeps equal elements from the first input ahead of equal elements from the second.

Common mistakes

Forgetting one tail loop.
Assuming inputs are sorted without stating the precondition.

Follow-up challenge

Merge from the back into the spare space of the first array.

Related Arrays exercises

Practice all Arrays exercises · Run this idea in the Java compiler