Merge Two Sorted Arrays In Java 8

Merging two sorted arrays is a common programming challenge that involves combining elements from two separate, already ordered arrays into a single, new sorted array. This task is fundamental in computer science, often appearing in algorithms like Merge Sort and various data processing scenarios.

In this article, you will learn how to efficiently merge two sorted arrays in Java 8, exploring different approaches from manual manipulation to leveraging the Stream API.

Problem Statement

Given two arrays, arr1 and arr2, both of which are sorted in ascending order, the goal is to create a new array that contains all elements from both arr1 and arr2, also sorted in ascending order. The challenge lies in performing this merge efficiently, ideally without completely re-sorting the entire combined array, as the input arrays are already sorted.

For instance, if arr1 = {1, 3, 5} and arr2 = {2, 4, 6}, the desired output is mergedArr = {1, 2, 3, 4, 5, 6}.

Example

Let's consider a simple case: int[] arr1 = {10, 20, 30}; int[] arr2 = {15, 25, 35, 40};

The expected output after merging these two arrays while maintaining sorted order is: {10, 15, 20, 25, 30, 35, 40}

Background & Knowledge Prerequisites

To effectively understand and implement the solutions, you should have a basic understanding of:

• Java Array Basics: How to declare, initialize, and access elements in arrays.
• Loops: for and while loops for iteration.
• Conditional Statements: if-else for decision-making.
• Methods: Defining and calling methods in Java.
• Java 8 Features (for Stream API approach): Basic familiarity with streams, IntStream, concat, and sorted.

Use Cases or Case Studies

Merging sorted arrays is a core operation in various applications:

• Database Systems: Combining results from two sorted query outputs.
• File Systems: Merging sorted log files or data records.
• Data Analysis: Consolidating sorted datasets from different sources for further processing.
• Algorithms: It's the central step in the Merge Sort algorithm, an efficient sorting technique.
• Event Scheduling: Combining sorted lists of events from different calendars into a single chronological timeline.

Solution Approaches

Here are three distinct approaches to merge two sorted arrays in Java 8, ranging from manual iterative methods to more modern stream-based solutions.

Approach 1: Two Pointers (Manual Merge)

This is the most efficient and classic approach. It uses two pointers, one for each input array, to compare elements and add the smaller one to the result array.

• Summary: Iteratively compare elements from both arrays using pointers, adding the smallest element to a new result array until all elements are merged.
• Code Example:

// Merge Two Sorted Arrays using Two Pointers
public class Main {
    public static void main(String[] args) {
        int[] arr1 = {10, 20, 30};
        int[] arr2 = {15, 25, 35, 40};

        int[] mergedArray = mergeSortedArraysTwoPointers(arr1, arr2);

        System.out.print("Merged Array (Two Pointers): ");
        for (int num : mergedArray) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static int[] mergeSortedArraysTwoPointers(int[] arr1, int[] arr2) {
        // Step 1: Calculate the total length of the new array
        int[] mergedArray = new int[arr1.length + arr2.length];

        // Step 2: Initialize pointers for arr1, arr2, and mergedArray
        int i = 0; // Pointer for arr1
        int j = 0; // Pointer for arr2
        int k = 0; // Pointer for mergedArray

        // Step 3: Iterate while both pointers are within their array bounds
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] <= arr2[j]) {
                mergedArray[k++] = arr1[i++];
            } else {
                mergedArray[k++] = arr2[j++];
            }
        }

        // Step 4: Add remaining elements from arr1 (if any)
        while (i < arr1.length) {
            mergedArray[k++] = arr1[i++];
        }

        // Step 5: Add remaining elements from arr2 (if any)
        while (j < arr2.length) {
            mergedArray[k++] = arr2[j++];
        }

        // Step 6: Return the merged array
        return mergedArray;
    }
}

Run

• Sample Output:

Merged Array (Two Pointers): 10 15 20 25 30 35 40

• Stepwise Explanation:

1. A new array mergedArray is created with a size equal to the sum of the lengths of arr1 and arr2.
2. Three pointers (i, j, k) are initialized to 0. i for arr1, j for arr2, and k for mergedArray.
3. A while loop runs as long as both i and j are within the bounds of their respective arrays.
4. Inside the loop, arr1[i] and arr2[j] are compared. The smaller element is placed into mergedArray[k], and its respective pointer (i or j) and the k pointer are incremented.
5. After the main loop, one of the arrays might have remaining elements. Two additional while loops handle adding any leftover elements from arr1 or arr2 to mergedArray.
6. The mergedArray is then returned.

Approach 2: Concatenate and Sort

This approach is simpler to implement but generally less efficient for already sorted arrays, especially for large inputs, as it involves a full sort of the combined data.

• Summary: Create a new array, copy all elements from both input arrays into it, then sort the new array.
• Code Example:

import java.util.Arrays;

// Merge Two Sorted Arrays using Concatenate and Sort
public class Main {
    public static void main(String[] args) {
        int[] arr1 = {10, 20, 30};
        int[] arr2 = {15, 25, 35, 40};

        int[] mergedArray = mergeSortedArraysConcatenateSort(arr1, arr2);

        System.out.print("Merged Array (Concatenate & Sort): ");
        for (int num : mergedArray) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static int[] mergeSortedArraysConcatenateSort(int[] arr1, int[] arr2) {
        // Step 1: Create a new array with combined length
        int[] mergedArray = new int[arr1.length + arr2.length];

        // Step 2: Copy elements from arr1 to mergedArray
        System.arraycopy(arr1, 0, mergedArray, 0, arr1.length);

        // Step 3: Copy elements from arr2 to mergedArray, starting after arr1's elements
        System.arraycopy(arr2, 0, mergedArray, arr1.length, arr2.length);

        // Step 4: Sort the entire mergedArray
        Arrays.sort(mergedArray);

        // Step 5: Return the sorted merged array
        return mergedArray;
    }
}

Run

• Sample Output:

Merged Array (Concatenate & Sort): 10 15 20 25 30 35 40

• Stepwise Explanation:

1. A new mergedArray is created to hold all elements.
2. System.arraycopy() is used to efficiently copy all elements from arr1 into the beginning of mergedArray.
3. System.arraycopy() is used again to copy all elements from arr2 into mergedArray, starting at the index immediately after arr1's elements.
4. Finally, Arrays.sort() is called on the mergedArray to sort all combined elements.

Approach 3: Using Java 8 Streams

Java 8's Stream API provides a concise way to achieve this, especially for collections or when dealing with object arrays. For primitive int arrays, IntStream is used.

• Summary: Convert both arrays to streams, concatenate them, and then collect the results into a new array after sorting.
• Code Example:

import java.util.Arrays;
import java.util.stream.IntStream;

// Merge Two Sorted Arrays using Java 8 Streams
public class Main {
    public static void main(String[] args) {
        int[] arr1 = {10, 20, 30};
        int[] arr2 = {15, 25, 35, 40};

        int[] mergedArray = mergeSortedArraysStreams(arr1, arr2);

        System.out.print("Merged Array (Streams): ");
        for (int num : mergedArray) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static int[] mergeSortedArraysStreams(int[] arr1, int[] arr2) {
        // Step 1: Convert arr1 to an IntStream
        IntStream stream1 = Arrays.stream(arr1);

        // Step 2: Convert arr2 to an IntStream
        IntStream stream2 = Arrays.stream(arr2);

        // Step 3: Concatenate the two streams, sort, and convert back to an array
        int[] mergedArray = IntStream.concat(stream1, stream2)
                                     .sorted() // This sort is needed because concat doesn't preserve sorted order
                                     .toArray();

        // Step 4: Return the merged array
        return mergedArray;
    }
}

Run

• Sample Output:

Merged Array (Streams): 10 15 20 25 30 35 40

• Stepwise Explanation:

1. Arrays.stream(arr1) and Arrays.stream(arr2) convert the primitive int arrays into IntStream objects.
2. IntStream.concat(stream1, stream2) combines the two streams into a single stream. At this point, the combined stream is not necessarily sorted.
3. .sorted() is then called on the concatenated stream to sort all its elements.
4. .toArray() collects the elements from the sorted stream back into a new int array.

Conclusion

Merging two sorted arrays is a foundational task in programming, with multiple effective solutions in Java. The "Two Pointers" approach stands out for its optimal time complexity, making it ideal for performance-critical applications where input arrays are already sorted. While the "Concatenate and Sort" method is simpler to implement, it sacrifices efficiency by re-sorting the entire combined array. The "Java 8 Streams" approach offers a concise and functional style, though it still relies on a sort operation similar to the concatenate and sort method for correctness.

Summary

• Two Pointers Method: Most efficient for merging already sorted arrays (O(N+M) time complexity).
• Concatenate and Sort Method: Simpler to implement but less efficient (O((N+M)log(N+M)) time complexity).
• Java 8 Streams Method: Concise and functional, but internally performs a sort operation (similar complexity to concatenate and sort).
• Choose the "Two Pointers" method for best performance when inputs are guaranteed to be sorted.
• The Stream API offers a modern, readable alternative but doesn't inherently optimize for pre-sorted inputs without the sorted() intermediate operation.