Leetcode/F家--88. Merge Sorted Array(Merge Sort)

88. Merge Sorted Array(Merge Sort)

• Difficulty: Easy

https://leetcode.com/problems/merge-sorted-array/

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 nums1 and nums2 are m and n respectively.

Company: Microsoft Bloomberg Facebook

思路：就是MergeSort的Merge part，建一个tmp array把nums[1]的elements copy过去，
           compare tmp[i] vs nums2[j], store the smaller one in nums[1]
关键字：Merge Sort

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] tmp= new int [m];
        for(int i = 0;i < m;i++){
            tmp[i]=nums1[i];
        }
        int i=0,j=0,k=0;
        while (i<m && j<n){
            if(tmp[i]<nums2[j]){
                nums1[k]=tmp[i];
                i++;
            }else{
                nums1[k]=nums2[j];
                j++;
            }
            k++;
        }
        while (i<m) nums1[k++]=tmp[i++];
        while (j<n) nums1[k++]=nums2[j++];
    }
}

Full Merge sort
https://www.hackerrank.com/contests/hw1/challenges/merge-sort/copy-from/8324041
Sort function:
public void sort(int left, int right, int[] arr){
           if(left<right){
                      int mid = left + (right-left)/2;
                      sort(left,mid);
                      sort(mid+1,right);
                      merge(left,mid,right,arr);
          }
}