Merging Two Sorted Arrays in Java

Java Program for Merging Two Sorted Array

In this article, we will dive deep into how to merging two sorted arrays in Java, explore multiple methods, walk through code implementations, analyze the time and space complexities, and explain everything step by step with examples.

Merge two sorted array in Java programming

Merging Two Sorted Arrays In Java Programming

What Does Merge Two Sorted Arrays Mean?

Given two sorted arrays, the goal is to combine them into a single sorted array that maintains the non decreasing order.

  • Merging two sorted arrays in Java involves combining two sorted arrays into one sorted array.
  • This can be done efficiently by comparing the first element of each array and adding the smaller one to a new array.
  • Process is repeated until all elements from both arrays are added to the new array.

Here is an example:

First Array = [12, 18, 40, 60]
Second Array = [47, 56, 89, 90]

Merged Array = [12, 18, 40, 47, 56, 60, 89, 90]

Merging two-sorted arrays in Java
Merging two-sorted arrays in Java

Different Approaches for Merging Two Sorted Arrays

Here, we have share 3 approaches for Merging two sorted arrays with Time and Space complexity alongwith Example codes.

  1. Using Extra Space (Brute Force Method)
  2. Two Pointers Approach
  3. In Place Merge Without Extra Space (Advanced)

Method 1: Using Extra Spaces for Merging two sorted array

Algorithm:

  1. Create a result array of size n + m.
  2. Use two pointers i and j to iterate over arr1 and arr2.
  3. Compare arr1[i] and arr2[j]:
    • Add the smaller element to the result array.

    • Move the pointer of the array from which the element was taken.

  4. Copy remaining elements (if any).

  5. Return the result array.

Code:

Run

public class MergeSortedArrays {

    public static int[] mergeArrays(int[] arr1, int[] arr2) {
        int n = arr1.length, m = arr2.length;
        int[] result = new int[n + m];
        int i = 0, j = 0, k = 0;

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

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

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

        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};

        int[] merged = mergeArrays(arr1, arr2);
        System.out.print("Merged Array: ");
        for(int num : merged) {
            System.out.print(num + " ");
        }
    }
}

Output:

Merged Array: 1 2 3 4 5 6 7 8

Method 2: Using Two Pointers for Merging two sorted array

Algorithm:

  1. Initialize two pointers:
    • i = 0 to traverse the first array (arr1)

    • j = 0 to traverse the second array (arr2)

  2. While both i < arr1.length and j < arr2.length:

    • Compare arr1[i] and arr2[j].

    • If arr1[i] <= arr2[j], print arr1[i] and increment i.

    • Else, print arr2[j] and increment j.

  3. After the loop ends, one of the arrays may still have elements left:

    1. Print the remaining elements in arr1 (from i to end)

    2. Print the remaining elements in arr2 (from j to end)

  4. The merged elements will be printed in sorted order without using any extra array.

Code:

Run

public class MergePrint {

    public static void mergeAndPrint(int[] arr1, int[] arr2) {
        int i = 0, j = 0;
        while(i < arr1.length && j < arr2.length) {
            if(arr1[i] <= arr2[j]) {
                System.out.print(arr1[i++] + " ");
            } else {
                System.out.print(arr2[j++] + " ");
            }
        }

        while(i < arr1.length) {
            System.out.print(arr1[i++] + " ");
        }

        while(j < arr2.length) {
            System.out.print(arr2[j++] + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {10, 20, 30};
        int[] arr2 = {5, 15, 25, 35};

        System.out.print("Merged Output: ");
        mergeAndPrint(arr1, arr2);
    }
}

Output:

Merged Output: 5 10 15 20 25 30 35

Method 3: Using In Place Merge (Without Extra Array) - Advanced Method

This method is only possible when one of the arrays has extra space (like a buffer at the end), or you’re dealing with data structures like ArrayList.

Otherwise, Java arrays are fixed size.

Let’s assume arr1 has size n + m, where the last m elements are empty (0), and arr2 has m elements.

Algorithm:

  1. Start from the end of both arrays.
  2. Fill from the end of arr1.
  3. Place the largest element at the last position, then move backward.

Code:

Run
public class InPlaceMerge {

    public static void merge(int[] arr1, int n, int[] arr2, int m) {
        int i = n - 1;
        int j = m - 1;
        int k = n + m - 1;

        while(i >= 0 && j >= 0) {
            if(arr1[i] > arr2[j]) {
                arr1[k--] = arr1[i--];
            } else {
                arr1[k--] = arr2[j--];
            }
        }

        while(j >= 0) {
            arr1[k--] = arr2[j--];
        }
    }

    public static void main(String[] args) {
        int[] arr1 = new int[10];
        arr1[0] = 1; arr1[1] = 3; arr1[2] = 5; arr1[3] = 7;
        int n = 4;

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

        merge(arr1, n, arr2, m);

        System.out.print("In-place Merged Array: ");
        for(int i = 0; i < n + m; i++) {
            System.out.print(arr1[i] + " ");
        }
    }
}

Output:

In-place Merged Array: 1 2 3 4 5 6 7 8

Edge Cases to Consider for Merging Sorted Arrays

  1. One array is empty:
    arr1 = {}, arr2 = {1,2,3} → Output: {1,2,3}
  2. Arrays contain duplicates:
    arr1 = {1,2,2}, arr2 = {2,3} → Output: {1,2,2,2,3}
  3. Arrays already merged:
    arr1 = {1,2}, arr2 = {3,4} → Output: {1,2,3,4}

Difference between methods for merging sorted array

Method for MergingExtra Space usedTime ComplexitySpace ComplexityConclusion
Brute Force (New Array)YesO(n + m)O(n + m)Simple and safe
Two Pointers (Print Only)NoO(n + m)O(1)Efficient if no storage needed
In-Place MergeNo (if buffer exists)O(n + m)O(1)Efficient but needs buffer space

Conclusion

Merging two sorted arrays is a fundamental problem that enhances your understanding of array traversal, pointer logic, and space optimization.

We explored three methods:

  1. Beginner friendly: using extra space.
  2. Optimized: two pointer without extra storage.
  3. Advanced: in place merging.

Each approach has its use case depending on the requirements of space, efficiency, and real time application.

FAQ's related to Merging Sorted Arrays

Answer:

Fastest way to merge them is by using the Two-Pointer Technique: similar to the merge step in Merge Sort.

Answer:

This is a trick question because all sorting involves some kind of sorting logic, even if you’re not explicitly calling Arrays.sort() or Collections.sort().

Answer:

Java 8 introduced the Stream API, which allows a functional, declarative approach to processing data. You can merge two unsorted arrays and sort them using Stream.concat() and sorted().

Answer:

In place Merge Sort using a single array (without a second helper array) is challenging, because the merge step usually needs extra space.

However, a workaround is possible by:

  1. Recursively dividing the array.
  2. Merging sorted halves manually, without using extra space (at the cost of more complex code and higher runtime constants).

But for clarity and practicality, we typically use a temporary array during the merge step.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription