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:

- Initialize two pointers,
`p1`

and`p2`

, at the last valid elements of`nums1`

and`nums2`

respectively. - Initialize a pointer
`p`

at the end of`nums1`

, which is the last position where elements can be inserted. - Compare
`nums1[p1]`

and`nums2[p2]`

. Insert the larger element at`nums1[p]`

and decrement the respective pointer. - 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

- We start by defining a class named
`MergeSortedArray`

. - 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`

. - 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.

- We start a
`while`

loop that continues until either`p1`

or`p2`

becomes less than 0. - 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`

. - After inserting an element, we decrement the pointer
`p`

to move to the next position in the merged array. - 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`

. - In the
`main`

method, we initialize`nums1`

with enough space to accommodate the merged elements. We also initialize`nums2`

. - We call the
`merge`

method with the appropriate parameters to merge`nums2`

into`nums1`

. - 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.