Section3 Daily Coding 18_mergeSort

문제

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

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length 100,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 병합 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

let output = mergeSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

힌트

• 병합 정렬은 표준 라이브러리에서 정렬을 구현할 때 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘입니다. 병합 정렬은 다음과 같은 알고리즘을 사용합니다.
  1. N의 길이를 가진 배열 리스트를 1의 길이를 가진 "부분 리스트"가 N개 모인 것으로 취급합니다.
  2. 인접한 부분 리스트들을 정렬하여 2의 길이를 가진 부분 리스트로 병합합니다.
  3. 2의 길이를 가진 인접한 부분 리스트들을 4의 길이를 가진 부분 리스트로 합칩니다.
  4. 하나의 정렬된 리스트가 될 때까지 위 과정을 반복합니다.
  5. N이 홀수라면, 첫 번째 병합 때 1의 길이를 가진 부분 리스트를 남깁니다.
• 병합 정렬은 두 가지 방식으로 구현 가능합니다. 재귀적 접근(위->아래) 그리고 반복적 접근(아래->위)

반복적 접근

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]

재귀적 접근

1. 주어진 배열을 절반으로 나눕니다. 4, 7, 4, 3, 9, 1, 2 -> 4, 7, 4, 3, 9, 1, 2
2. 두 배열이 재귀적으로 정렬됩니다. 4, 7, 4 -> 4, 4, 7 -> 1, 2, 3, 9
3. 두 배열이 병합됩니다. 4, 7, 4, 3, 9, 1, 2 -> 1, 2, 3, 4, 4, 7, 9

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

1. 주어진 배열을 절반으로 나눕니다. 4, 7, 4 -> 4, 7, 4
2. 두 배열이 재귀적으로 정렬됩니다. 4 -> 4 -> 4, 7
3. 두 배열이 병합됩니다. 4, 4, 7 -> 4, 4, 7

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

1. 주어진 배열을 절반으로 나눕니다. 7, 4 -> 7, 4
2. 두 배열이 재귀적으로 정렬됩니다. 7 -> 7 -> 4
3. 두 배열이 병합됩니다. 7, 4 -> 4, 7

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

Reference Code

const merge = function (left, right) {
  let merged = [];
  let leftIdx = 0,
    rightIdx = 0;
  const size = left.length + right.length;

  for (let i = 0; i < size; i++) {
    if (leftIdx >= left.length) {
      merged.push(right[rightIdx]);
      rightIdx++;
    } else if (rightIdx >= right.length || left[leftIdx] <= right[rightIdx]) {
      merged.push(left[leftIdx]);
      leftIdx++;
    } else {
      merged.push(right[rightIdx]);
      rightIdx++;
    }
  }

  return merged;
};

const mergeSort = function (arr) {
  if (arr.length < 2) return arr;
  const middle = parseInt(arr.length / 2);
  const left = mergeSort(arr.slice(0, middle));
  const right = mergeSort(arr.slice(middle));
  const merged = merge(left, right);
  return merged;
};

내코드

const mergeSort = function (arr) {
  // 쪼갠 배열에서 오름차순으로 정렬시켜줄 함수 merge 생성
	const merge = (left, right) => {
      const resultArr = [];
      let leftIndex = 0;
      let rightIndex = 0;
      while(leftIndex < left.length && rightIndex < right.length) {
      	if(left[leftIndex] < right[rightIndex]){
          resultArr.push(left[leftIndex]);
          leftIndex++;
        } else {
          resultArr.push(right[rightIndex]);
          rightIndex++;
        }
      }
      // left, right 둘 중 하나의 배열의 숫자가 남고 while문이 끝날 수 있기 때문에
      // 마지막으로 concat으로 뒤에 남은 큰 숫자들을 넣어준다.
      // silce(Index)에서 배열의 마지막 Index라면 빈 배열을 넣게됨.
     return resultArr.concat(left.slice(leftIndex), right.slice(rightIndex));
    }
  if(arr.length < 2) return arr;
  let mid = Math.floor(arr.length/2);
  let leftArr = arr.slice(0, mid);
  let rightArr = arr.slice(mid);
  // 기존배열을 쪼개고 쪼개는 과정
  return merge(mergeSort(leftArr), mergeSort(rightArr));
}