[자바스크립트] 병합정렬

연결리스트 문제를 풀다가 병합 정렬을 적용해서 푸는 문제가 나왔는데 생각이 잘 안나서 병합정렬을 다시 풀어보았다.
전에 했던 건데 오랜만에 풀려니 헷갈려서 시간이 꽤 걸렸다.
이제 잊지 말아야지 ..!

문제

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

입출력 예시

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

output = mergeSort([-1, 5, 3, 4, 0])
console.log(output); // --> [ -1, 0, 3, 4, 5 ]

output = mergeSort([5, 6, 2, 1, 7, 8])
console.log(output); // --> [ 1, 2, 5, 6, 7, 8 ]

output = mergeSort([10, 3, 31, 4, 7, 15])
console.log(output); // --> [ 3, 4, 7, 10, 15, 31 ]

나의 풀이

정답 함수 내부에 2개의 함수를 추가해서(분리해서) 풀었다.
① left 배열과 right 배열로 절반으로 나누는 splitArray 함수와
② 이 둘의 각 요소들을 비교해서 하나로 다시 합쳐주는 merge 함수

// 1. 배열을 절반씩 left 배열과 right 배열로, 각 배열의 요소가 1개 이하일 때까지 나눈다.

const mergeSort = function (arr) {
   if (arr.length <= 1) return arr

  const [left, right] = splitArray(arr)

  const _left = mergeSort(left)
  const _right = mergeSort(right)

  return merge(_left, _right)
};

function splitArray(array) {
  const half = Math.ceil(array.length / 2)

  const left = array.slice(0, half)
  const right = array.slice(half)

  return [left, right]
}

// 2. 나눠진 left, right 배열의 요소들을 차례로 비교해서 작은 값을 꺼내서 answer 배열에 넣는다.
// 값을 비교할 때 한 쪽 배열의 요소가 0개면 나머지 배열을 그대로 넣어서 리턴한다.
// left, righ 각 배열 내부는 정렬되어 있다.

function merge(left, right) {
  let answer = []

  while (true) {
    if (left.length === 0) {
      answer.push(...right)
      break
    }
    if (right.length === 0) {
      answer.push(...left)
      break
    }

    if (left[0] <= right[0]) {
      answer.push(left.shift())
    } else if (right.length) {
      answer.push(right.shift())
    }
  }

  return answer
}

레퍼런스

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;
};

힌트

병합 정렬은 표준 라이브러리에서 정렬을 구현할 때 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘입니다. 병합 정렬은 다음과 같은 알고리즘을 사용합니다.

N의 길이를 가진 배열 리스트를 1의 길이를 가진 "부분 리스트"가 N개 모인 것으로 취급합니다.
인접한 부분 리스트들을 정렬하여 2의 길이를 가진 부분 리스트로 병합합니다.
2의 길이를 가진 인접한 부분 리스트들을 4의 길이를 가진 부분 리스트로 합칩니다.
하나의 정렬된 리스트가 될 때까지 위 과정을 반복합니다.
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]]

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

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

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

재귀적 접근

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

[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단계에서 병합이 되기 때문에 최종적으로 정렬된 하나의 배열이 리턴됩니다.