[알고리즘] mergeSort

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 한다.

병합 정렬을 이용해야 한다고 하는데, 문제의 설명은 아래와 같았다.

🚩 병합정렬
N의 길이를 가진 배열 리스트를 1의 길이를 가진 "부분 리스트"가 N개 모인 것으로 취급한다.
인접한 부분 리스트들을 정렬하여 2의 길이를 가진 부분 리스트로 병합한다.
2의 길이를 가진 인접한 부분 리스트들을 4의 길이를 가진 부분 리스트로 합친다.
하나의 정렬된 리스트가 될 때까지 위 과정을 반복함.
N이 홀수라면, 첫 번째 병합 때 1의 길이를 가진 부분 리스트를 남김.

솔직히 설명만 봐서는 이해가 잘 안 갔는데, 그럴 것을 알았는지... 예시를 들어준 바는 아래와 같다.

병합 정렬 방법에는 재귀적 접근(위->아래) 그리고 반복적 접근(아래->위) 이렇게 두 가지가 있다고 한다.

//재귀적 접근

//기본적인 방법은 아래 1~3단계를 반복하는 것.
//1.주어진 배열을 절반으로 나눕니다.
[4, 7, 4, 3, 9, 1, 2] -> [4, 7, 4], [3, 9, 1, 2]

//2.두 배열이 재귀적으로 정렬됩니다.
[4, 7, 4] -> [4, 4, 7]
[3, 9, 1, 2] -> [1, 2, 3, 9]

//3.두 배열이 병합됩니다.
[4, 7, 4], [3, 9, 1, 2] -> [1, 2, 3, 4, 4, 7, 9]



//2단계에서 나뉘어진 각각의 배열 
[4, 7, 4] [3, 9, 1, 2]
//에 대해서도 1-3번의 과정이 재귀적으로 똑같이 진행됩니다.

//주어진 배열을 절반으로 나눕니다.
[4, 7, 4] -> [4], [7, 4]

//두 배열이 재귀적으로 정렬됩니다.
[4] -> [4]
[7, 4] -> [4, 7]

//두 배열이 병합됩니다.
[4], [4, 7] -> [4, 4, 7]



//이 과정의 2단계에서 나뉘어진 
[4, 7]
//에 대해서도 재귀가 호출됩니다.
//[4]는 원소가 하나이기 때문에 정렬하지 않아도 되겠죠?

//주어진 배열을 절반으로 나눕니다.
[7, 4] -> [7], [4]

//두 배열이 재귀적으로 정렬됩니다.
[7] -> [7]
[4] -> [4]

//두 배열이 병합됩니다.
[7], [4] -> [4, 7]


//모든 재귀 호출이 완료되면 3단계에서 병합이 되기 때문에 
//최종적으로 정렬된 하나의 배열이 리턴됩니다.

//반복적 접근 
//1. 주어진 배열이 "정렬된" 부분 리스트로 나뉘어집니다.
 [4,7,4,3,9,1,2] -> [[4],[7],[4],[3],[9],[1],[2]]

//2. 인접한 부분 리스트 2개가 정렬된 부분 리스트로 병합됩니다.
 [[4],[7],[4],[3],[9],[1],[2]] -> [[4,7],[3,4],[1,9],[2]]

//2. 병합 과정 (반복) :
 [[4,7],[3,4],[1,9],[2]] -> [[3,4,4,7], [1,2,9]]

//2. 병합 과정 (반복) :
 [[3,4,4,7], [1,2,9]] -> [[1,2,3,4,4,7,9]]

//3. 마무리 : 정렬된 배열이 리턴됩니다.
 [1,2,3,4,4,7,9]

래퍼런스 코드는 재귀를 이용해서 풀고 있는데,
분석해본 것은 아래와 같다.

//병합하는 함수를 만든다 merge 
const merge = function (left, right){
 let merged = [];
  let leftIdx = 0,
    rightIdx = 0;
  const size = left.length + right.length;//인자로 받은 left배열과 right 배열의 길이 합

//반복문을 돌리면서 Idx에 해당하는 값들을 비교해서 merged에 담는 것이 목표 
//반복문은 원 배열인 arr의 길이만큼 반복될 것임
 for (let i = 0; i < size; i++) {
    if (leftIdx >= left.length) {
    //leftIdx가 left.length와 같거나 그보다 커지게 되면 
    //right[rightIdx]를 merged에 push 한다. 
    //rightIdx를 1 증가시킨다 
   merged.push(right[rightIdx]);
      rightIdx++;
  }else if (rightIdx >= right.length || left[leftIdx] <= right[rightIdx]) {
    //rightIdx의 값이 right배열의 길이와 같거나 클 때
    //혹은 left배열의 leftIdx 값이 right의 rightIdx 값보다 작거나 같을 때 
    //left[leftIdx]를 merged에 push하고
    //leftIdx를 1 증가시킨다
    merged.push(left[leftIdx]);
      leftIdx++;
    } else {
      //그 외에는 right[rightIdx]를 merged에 push하고 rightIdx를 1 증가시킨다.
      merged.push(right[rightIdx]);
      rightIdx++;
    }
 }
    return merged;
}


const mergeSort = function (arr) {
  if(arr.length <= 1){
    return arr;
  }//재귀 탈출 조건 : 배열의 길이가 1일 때 탈출한다. 
  const half = parseInt(arr.length / 2); 
  const left = mergeSort(arr.slice(0,half));
  const right = mergeSort(arr.slice(half));
  const merged = merge(left, right);
   return merged;

};