Merge Sorted Array (JS)

Merge Sort

언제 쓰나?
두 개의 정렬된 array를 합치고자 할 때


관련 문제

문제 분석
1. nums2를 nums1에다 넣어 정렬
2. nums1은 공간이 이미 확보
3. m,n으로 각 배열에 원소가 몇 개가 있는지 알려주는 상황


풀이

빨간색과 초록색 포인터의 값을 비교하여 파란색 포인터에 값을 넣는 operation을 반복 수행한다.
Time Complexity = O(n+m)
Space Complexity = O(1)

var merge = function(nums1, m, nums2, n) {
 // 빨간 포인터
 let num1Idx = m-1;
 // 초록 포인터
 let num2Idx = n-1;
 // 파랑 포인터
 let wIdx = nums1.length -1;
 if(num2Idx<0){
     return;
 }
 while(0<= num1Idx && 0<=num2Idx){
     let num1 = nums1[num1Idx];
     let num2 = nums2[num2Idx];
     if(num2<=num1) {
         let num = num1;
         nums1[wIdx] = num;
         num1Idx--;
         wIdx--;
     }else{
         let num = num2;
         nums1[wIdx] = num;
         num2Idx--;
         wIdx--;
     }
 }
while(0<=num2Idx){
    nums1[wIdx] = nums2[num2Idx];
    num2Idx--;
    wIdx--;
}
};