How to merge two sorted array?

Question

Question is ==> You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

What is wrong in my code???

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = 0; 
        int l = 0;
        for(int i=0; i<(m+n); i++){
            if(k > (m-1)){
                nums1[i] = nums2[l];
                l += 1;
            }
            else if(nums1[k] <= nums2[l]){
                nums1[i] = nums1[k];
                k += 1;
            }
            else {
                nums1[i] = nums2[l];
                l += 1;
            }
        }
    }
}

Your input

[1,2,3,0,0,0]
3
[2,5,6]
3

My output

[1,2,2,2,5,6]

Expected output

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

Answer 1

You're overriding values in nums1 while merging arrays and this way you're replacing some numbers from nums1 before you checked them with numbers from nums2. In your example when you're merging there is a moment when you have i=2, k=2, l=0 and your nums1 look as following: nums1=[1,2,3,0,0,0]. So far it's looking good but now you have nums1[k] with value 3 and nums2[l] with value 2 so you're setting nums1[i]=nums2[l], i.e. nums1[2]=nums2[0]. This way you're replacing 3 in nums1 with 2 from nums2 so you just lost your 3 from original nums1 and you won't be able to put it in the final array.

There are two solutions to this issue:

1. Auxillary (temporary) array where you will put your numbers and in the end this array will be merged and sorted arrays of nums1 and nums2 so you can then just copy this array into nums1 to have all the numbers merged and sorted in nums1.
2. Each time you put a number from nums2 into nums1 into i position, move all unprocessed numbers from original nums1 (numbers from i position to last non-zero number from nums1) by one position forward so that your number from i position will be stored at i+1 position, number from previous i+1 position will be at i+2 position etc. Just keep proper order of moving those numbers, i.e. move them starting from last non-zero number and going back to avoid losing any numbers during this process.

Each of these solutions have its own advantages and disadvantages related to time and space complexity but as an example I'm showing how to implement the first approach:

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] mergedAndSortedArray = new int[m + n];
    int k = 0;
    int l = 0;
    for(int i=0; i<(m+n); i++){
        if(k > (m-1)){
            mergedAndSortedArray[i] = nums2[l];
            l += 1;
        }
        else if(nums1[k] <= nums2[l]){
            mergedAndSortedArray[i] = nums1[k];
            k += 1;
        }
        else {
            mergedAndSortedArray[i] = nums2[l];
            l += 1;
        }
    }

    // copy final merged and sorted array to nums1, you can also do this using `for` loop but this is more efficient way
    System.arraycopy(mergedAndSortedArray, 0, nums1, 0, m + n);
}

Answer 2

Because in your if clause inside your for loop, you are basically putting the second array at the end of the first without testing if its numbers have already been used.

Answer 3

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        index = 0
        for x in range(len(nums1)):
            if index>=n:
                break
            if nums1[x]==0:
                nums1[x]=nums2[index]
                index+=1
        nums1.sort()