Merge Sorted Array: Efficiently Combining Two Sorted Arrays

Merging sorted arrays is a common problem in programming, especially in the context of algorithms. This blog post will delve into the problem of merging two sorted integer arrays, known as “Merge Sorted Array”. We will explore approaches to solve this problem, focusing on an efficient method that leverages the two-pointer technique. By the end, you will have a solid understanding of how to implement this solution in Java.

Understanding the Problem

The task is to merge two sorted integer arrays, nums1 and nums2, into one sorted array. The first array, nums1, has a size of m + n, where m is the number of initialized elements and n is the number of elements in nums2. The challenge is to merge these arrays efficiently.

Example Scenario

Consider the following example:

nums1: [1, 2, 3, 0, 0, 0]
nums2: [2, 5, 6]

After merging, nums1 should become:

nums1: [1, 2, 2, 3, 5, 6]

Approaches to Solve the Problem

There are several approaches to tackle the “Merge Sorted Array” problem. The basic approach is straightforward, but it is not the most efficient. Let’s explore both the naive and optimized methods.

Naive Approach

The naive approach involves copying all elements of nums2 into nums1, followed by sorting the combined array. This method is simple but inefficient:

Time Complexity: O(k log k), where k is m + n.
Space Complexity: O(1), since we are storing it in the original array.

Optimized Approach: Two-Pointer Technique

To improve efficiency, we can use the two-pointer technique. This method reduces the time complexity to O(k) while maintaining O(1) space complexity. The main idea is to fill nums1 starting from the end, comparing elements from nums1 and nums2.

How the Two-Pointer Technique Works

We will maintain three pointers:

p1: Points to the last initialized element in nums1 (m – 1).
p2: Points to the last element in nums2 (n – 1).
i: Points to the last position in nums1 (m + n – 1).

The process is as follows:

Compare the elements pointed to by p1 and p2.
Place the larger element at index i in nums1.
Decrement the respective pointers.
Repeat until all elements from nums2 are merged.

Java Implementation

Now, let’s implement the two-pointer approach in Java:

public class MergeSortedArray {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1; // Last initialized element in nums1
        int p2 = n - 1; // Last element in nums2
        int i = m + n - 1; // Last position in nums1

        // While there are elements in nums2
        while (p2 >= 0) {
            // Check if p1 is valid and compare values
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[i--] = nums1[p1--];
            } else {
                nums1[i--] = nums2[p2--];
            }
        }
    }

    public static void main(String[] args) {
        MergeSortedArray merger = new MergeSortedArray();
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 5, 6};
        merger.merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1)); // Output: [1, 2, 2, 3, 5, 6]
    }
}

Edge Cases

When dealing with merging sorted arrays, it’s important to consider edge cases:

If nums1 is empty (m = 0), simply copy nums2 into nums1.
If nums2 is empty (n = 0), nums1 remains unchanged.
If both arrays are empty, the result is also an empty array.

Example Edge Case

For instance, if:

nums1: []
nums2: [1]

After merging, nums1 should become:

nums1: [1]

Conclusion

The “Merge Sorted Array” problem can be solved efficiently using the two-pointer technique. This method not only reduces time complexity but also ensures that the space complexity remains minimal. By understanding this approach and its implementation in Java, you can tackle similar problems effectively.

You can explore more about data structures through our Tree Data Structure and Graph Data Structure playlists.

Happy coding!

Merge Sorted Array