Tutorial: Merge Sorted Array – Java Solution

In this tutorial, we will delve into the “Merge Sorted Array” problem and provide a comprehensive Java solution. This problem is a classic algorithmic challenge that tests your ability to merge two sorted arrays in an efficient manner. We will start by understanding the problem statement, breaking it down into smaller components, and then proceed to implement the solution step by step.

Problem Statement

Given two sorted arrays, nums1 and nums2, the task is to merge nums2 into nums1 as one sorted array. The merged array should be sorted in non-decreasing order.

Note:

• nums1 has enough space to hold additional elements from nums2.
• The number of elements initialized in nums1 and nums2 are m and n respectively.

Approach Overview

To merge two sorted arrays efficiently, we need to compare the elements of both arrays and place them in the correct positions in the final merged array. Since nums1 has enough space to accommodate all elements, we can start from the end of both arrays and work backwards. This approach avoids overwriting values in nums1 that haven’t been processed yet.

The steps involved in this approach are as follows:

1. Initialize two pointers, p1 and p2, at the last valid elements of nums1 and nums2 respectively.
2. Initialize a pointer p at the end of nums1, which is the last position where elements can be inserted.
3. Compare nums1[p1] and nums2[p2]. Insert the larger element at nums1[p] and decrement the respective pointer.
4. Repeat step 3 until all elements have been merged.

Let’s now implement this approach in Java.

Java Implementation

public class MergeSortedArray {

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1; // Pointer for nums1
        int p2 = n - 1; // Pointer for nums2
        int p = m + n - 1; // Pointer for merged array

        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }

        // Copy remaining elements from nums2 if any
        System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
    }

    public static void main(String[] args) {
        int[] nums1 = new int[6]; // Initialize nums1 with enough space
        nums1[0] = 1;
        nums1[1] = 3;
        nums1[2] = 5;
        int m = 3;

        int[] nums2 = {2, 4, 6};
        int n = 3;

        merge(nums1, m, nums2, n);

        // Print the merged array
        for (int num : nums1) {
            System.out.print(num + " ");
        }
    }
}

Step-by-Step Explanation

1. We start by defining a class named MergeSortedArray.
2. In the merge method, we take four parameters: nums1, m, nums2, and n. Here, nums1 is the target array, m is the number of initialized elements in nums1, nums2 is the array to be merged, and n is the number of elements in nums2.
3. We initialize three pointers:

• p1 points to the last valid element in nums1.
• p2 points to the last element in nums2.
• p points to the last position in the merged array.

1. We start a while loop that continues until either p1 or p2 becomes less than 0.
2. Inside the loop, we compare the elements at nums1[p1] and nums2[p2]. If nums1[p1] is greater, we insert it at nums1[p] and decrement p1. Otherwise, we insert nums2[p2] at nums1[p] and decrement p2.
3. After inserting an element, we decrement the pointer p to move to the next position in the merged array.
4. Once the loop is done, there might be some remaining elements in nums2 that need to be inserted into nums1. We use the System.arraycopy method to copy the remaining elements from nums2 to the beginning of nums1.
5. In the main method, we initialize nums1 with enough space to accommodate the merged elements. We also initialize nums2.
6. We call the merge method with the appropriate parameters to merge nums2 into nums1.
7. Finally, we iterate through the merged array and print the elements.

Time and Space Complexity Analysis

The time complexity of this solution is O(m + n), where m is the number of elements in nums1 and n is the number of elements in nums2. We only traverse through the arrays once.

The space complexity is O(1), as we are not using any extra space that scales with the input size. We are performing the merging in-place.

Conclusion

In this tutorial, we explored the “Merge Sorted Array” problem and provided a detailed Java solution. We discussed the problem statement, formulated an approach, implemented the solution step by step, and analyzed the time and space complexity of the solution. By following this tutorial, you should now have a clear understanding of how to efficiently merge two sorted arrays in Java while maintaining the sorted order.