Merge Sorted Array

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Approach

• If nums1 and nums2 are empty then return. Nothing cane be merged.
• Copy m elements from nums1 into a new array say nums1Replica.
• Initialize the indexes of all 3 arrays to 0:
• Index of nums1Replica is i
• Index of nums2 is j
• Index of nums1 is k
• Start to compare each element in nums1Replica and nums2 until i and j are less than m and n respectively.
• If nums1Replica[i] <= nums2[j], copy nums1Replica[i] into nums1[k] & increment i, k
• If nums1Replica[i] > nums2[j], copy nums2[j] into nums1[k] & increment j, k
• When either i >= m OR j >= n, copy the remaining array into nums1 (sorted array).

Run Time Complexity

Worst case run time complexity is O(n) which includes:

Copying m elements into a new array = O(n)

Traversing through nums1Replica and nums2 = O(n)

Copying the remaining elements into the sorted array = O(n)

Code

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(nums1.length == 0 && nums2.length == 0){
            return;
        }
        
        int[] nums1Replica = copyArray(nums1, m);
        int index1 = 0;
        int index2 = 0;
        int index3 = 0;
        while(index1 < m && index2 < n){
            if(nums1Replica[index1] <= nums2[index2]){
                nums1[index3] = nums1Replica[index1];
                index1++;
                index3++;
            }
            else{
                nums1[index3]= nums2[index2];
                index2++;
                index3++;
            }
        }
        if(index1 < m){
            nums1 = getSorted(nums1Replica,index1,nums1,index3);
        }else{
            nums1 = getSorted(nums2,index2,nums1,index3);
        }
    }
    
/*Return an array of m elements in the input array*/
    private int[] copyArray(int[] nums1, int m){
        int[] nums1Replica = new int[m];
        for(int i = 0; i < m; i++){
            nums1Replica[i] = nums1[i];
        }
        return nums1Replica;
    }
    
/* Return a sorted array by copying the elements from the remaining array*/    
private int[] getSorted(int[] remain,int index,int[] sorted,int index3){
        for(int i = index; i < remain.length; i++){
            sorted[index3] = remain[i];
            index3++;
        }
        return sorted;
    }
}