Merging Two Sorted Arrays in Java

By
Shivam Gupta
-
90
Merging Two Sorted Arrays in Java
Advertisement

Title: Merging Two Sorted Arrays in Java

Merging two sorted arrays into a single array is a common operation in programming, especially when dealing with data structures and algorithms. In this guide, we’ll explore how to merge two sorted arrays efficiently using Java. We’ll provide a detailed explanation, examples, and code snippets to help you understand the logic and implementation.

Understanding the Problem

When we have two arrays that are already sorted in ascending order, merging them means combining their elements into a single sorted array. The resulting array should also be in ascending order.

For example, if we have two sorted arrays:

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

The merged array should be:

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

Approach to Merge Two Sorted Arrays

To merge two sorted arrays efficiently, we can use a simple approach that utilizes two pointers. We’ll compare elements from both arrays and insert them into the new array in ascending order.

Here are the steps:

  1. Initialize three pointers: one for each input array (i for arr1, j for arr2), and one for the merged array (k).
  2. Compare elements at indices i and j of arr1 and arr2 respectively.
  3. Insert the smaller of the two elements into the merged array at index k.
  4. Increment the pointer of the array from which the element was inserted (i or j).
  5. Increment k to move to the next position in the merged array.
  6. Repeat steps 2-5 until we reach the end of either arr1 or arr2.

Java Program to Merge Two Sorted Arrays

Let’s implement the above approach in Java:

Java
public class MergeSortedArrays {

    public static int[] mergeArrays(int[] arr1, int[] arr2) {
        int n1 = arr1.length;
        int n2 = arr2.length;
        int[] merged = new int[n1 + n2];
        int i = 0, j = 0, k = 0;

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

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

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

        return merged;
    }

    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.println("Merged Array: " + Arrays.toString(merged));
    }
}

Explanation of the Program

  • We define a method mergeArrays that takes two sorted arrays arr1 and arr2 as input and returns the merged array.
  • We initialize pointers i, j, and k to track positions in arr1, arr2, and merged array respectively.
  • We compare elements at indices i and j and insert the smaller element into the merged array at index k.
  • We then increment the respective pointers and k.
  • The process continues until we reach the end of either arr1 or arr2.
  • Finally, we return the merged array.

Examples

Let’s consider some examples to understand the program’s behavior:

  • For arr1 = {1, 3, 5, 7} and arr2 = {2, 4, 6, 8}, the merged array will be {1, 2, 3, 4, 5, 6, 7, 8}.
  • For arr1 = {2, 4, 6, 8} and arr2 = {1, 3, 5, 7}, the merged array will also be {1, 2, 3, 4, 5, 6, 7, 8}.

Additional Considerations

While the provided Java program offers a straightforward and efficient way to merge two sorted arrays, there are a few additional points to consider:

  1. Array Lengths: The program assumes that both input arrays arr1 and arr2 are sorted and have distinct elements. If the arrays have duplicate elements, the merged array will also contain duplicates.
  2. Edge Cases: It’s essential to handle edge cases, such as when one or both input arrays are empty (arr1.length == 0 or arr2.length == 0). In such cases, the program should handle these scenarios gracefully and return the appropriate result.
  3. Memory Efficiency: The program creates a new array merged of size n1 + n2 to store the merged elements. For large arrays or memory-constrained environments, this might not be the most memory-efficient approach. If memory is a concern, you could explore ways to optimize the memory usage.
  4. Complexity Analysis: The time complexity of the mergeArrays method is O(n1 + n2), where n1 and n2 are the lengths of the input arrays arr1 and arr2 respectively. This is because we iterate through each element of both arrays once to merge them. The space complexity is O(n1 + n2) as well, as we create a new array of size n1 + n2 to store the merged elements.

Example Usages

Here are some examples demonstrating how you can use the mergeArrays method:

Example 1: Merging Two Arrays

Java
int[] arr1 = {1, 3, 5, 7};
int[] arr2 = {2, 4, 6, 8};
int[] merged = mergeArrays(arr1, arr2);

System.out.println("Merged Array: " + Arrays.toString(merged));
// Output: Merged Array: [1, 2, 3, 4, 5, 6, 7, 8]

Example 2: Handling Empty Arrays

Java
int[] arr1 = {};
int[] arr2 = {2, 4, 6, 8};
int[] merged = mergeArrays(arr1, arr2);

System.out.println("Merged Array: " + Arrays.toString(merged));
// Output: Merged Array: [2, 4, 6, 8]

Example 3: Merging Arrays of Different Lengths

Java
int[] arr1 = {1, 3, 5};
int[] arr2 = {2, 4, 6, 8, 10};
int[] merged = mergeArrays(arr1, arr2);

System.out.println("Merged Array: " + Arrays.toString(merged));
// Output: Merged Array: [1, 2, 3, 4, 5, 6, 8, 10]

Conclusion

In this comprehensive guide, we’ve covered how to merge two sorted arrays into a single sorted array using Java. The mergeArrays method efficiently combines elements from both arrays while maintaining the sorted order. By following the provided explanation, examples, and code snippets, you now have a solid understanding of how to implement this functionality in your Java programs.

Remember to consider edge cases, optimize for memory efficiency when necessary, and analyze the time and space complexity of your implementation. With this knowledge, you can confidently tackle tasks that involve merging sorted arrays, such as implementing sorting algorithms, working with ordered data structures, or solving algorithmic challenges.

Feel free to use the provided Java program and examples in your own projects, adapting them as needed to suit your requirements. Happy coding!

You can learn more about Array and Sorting techniques: Arrays and Sorting

Latest Posts:

RELATED ARTICLESMORE FROM AUTHOR