LeetCode: Merge Sorted Array

 Problem statement is copy pasted from leetcode as it is:

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

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

 

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

 

Constraints:

• 0 <= n, m <= 200
• 1 <= n + m <= 200
• nums1.length == m + n
• nums2.length == n
• -109 <= nums1[i], nums2[i] <= 109

My Solution:

package madwani.sushil.leetcode.Jan_8_15_2021;

public class MergeSortedArray {
    public static void main(String[] args) {
        int [] nums1 = new int[] {1, 2, 3, 0, 0, 0};
        int [] nums2 = new int[] {2, 5, 6};
        int [] nums12 = new int[] {1};
        int [] nums22 = new int[] {};
        int [] nums13 = new int[] {4,0,0,0,0,0};
        int [] nums23 = new int[] {1,2,3,5,6};
        int [] nums14 = new int[] {1,2,4,5,6,0};
        int [] nums24 = new int[] {3};
        int [] nums15 = new int[] {0,0,3,0,0,0,0,0,0};
        int [] nums25 = new int[] {-1,1,1,1,2,3};
        merge1(nums1, 3, nums2, 3);
        merge1(nums12, 1, nums22, 0);
        merge1(nums13, 1, nums23, 5);
        merge1(nums14, 5, nums24, 1);
        merge1(nums15, 3, nums25, 6);
        System.out.println("done");
    }

    // its a single pass with O(1) space complexity
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        m = m-1; // pointer to last element of num1
        n = n-1; // pointer to last element of num2

        // total number of elements
        int i = nums1.length - 1;

        // iterating from end of each array till we reach start of any array
        while ( n >= 0 && m >=0) {
            if (nums2[n] > nums1[m]) {
                nums1[i--] = nums2[n--];
            } else {
                nums1[i--] = nums1[m--];
            }
        }
        // if second array is still left with the elements
        while (n >= 0) {
            nums1[i--] = nums2[n--];
        }
    }

    // with space complexity O(N)
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if ( n == 0) {
            return;
        }
        int i =0, j=0;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) i++;
            else {
                insert(nums1, i, nums2[j]);
                m++;
                j++;
            }
        }
        while (i < nums1.length && j < n) {
            if (nums1[i] !=0) i++;
            else nums1[i++] = nums2[j++];
        }

    }

    public static void insert(int[] nums1, int position, int tNum) {
        while (position < nums1.length) {
           int temp = nums1[position];
           nums1[position++] = tNum;
           tNum = temp;
        }
    }
}

Algorithm: Difference between Quick Sort and Merge Sort

1. Merge Sort is stable sort however Quick is not.
2. Worst case complexity for merge is O(nlogn) however for quick it is o(n*n)
3. Merger requires O(n) extra space for merging, however Quick does in place sorting.
4. Merge works well with all sizes of array, however Quick is good for smaller arrays for larger arrays it is inefficient as it does lots of comparison.
5. The Quick is internal nature means sorting happens in memory however Merge sort happens in auxiliary space i.e. it is external in nature.