자바스크립트로 합병정렬 구현 (merge sort in javascript)

Merge Sort?

합병정렬(merge sort)는 평균 시간복잡도 O(nlogn)의 비교 기반 정렬 알고리즘입니다. 대표적인 divide and conquer (분할정복) 알고리즘을 활용하여 구현하는 정렬 알고리즘 중 하나입니다. (Safari, Firefox의 Array.prototype.sort가 merge sort 알고리즘으로 구현되어 있습니다.) 좋은 성능을 가지고 있고, 구현하기 쉽고 이해하기도 쉬운 장점을 가진 정렬 알고리즘입니다.

합병정렬은 어떻게 동작할까요? 합병정렬은 하나의 정렬되지 않은 배열을 정렬하는 것보다 두 개의 정렬된 배열을 정렬하는 것이 더 효율적이다라는 아이디어로 시작합니다. 두 개의 정렬된 배열이 있다면, 하나씩 요소를 비교하고, 작은 값을 결과 배열에 하나씩 추가하기 시작합니다. A와 B의 배열이 있다고 생각해 봅시다. A[0]와 B[0]의 요소를 비교합니다. A[0] 요소가 더 작다면 A[0] 요소를 결과 배열에 넣습니다. A[1]과 B[0]를 비교합니다. B[0]가 더 작다면 B[0]를 결과 배열에 넣습니다. A[1]과 B[1]을 비교합니다. 이렇게 비교가 끝나면 결과 배열은 A와 B 배열의 비교 값에 대해서 정렬된 상태가 될 것입니다. (A배열과 B배열은 정렬된 상태라 추가적으로 정렬할 필요가 없다)

시간복잡도

• 최악 시간복잡도: O(nlogn)
• 평균 시간복잡도: O(nlogn)
• 최선 시간복잡도: O(nlogn)

구현 방법

구현 방법은 크게 3가지로 구성되어 있습니다.

1. 정렬되지 않은 하나의 배열을 단일 요소를 가진 배열이 될 때 까지 나눈다. (Divide)
2. 단일 요소를 가진 배열을 합친다. (conquer)
3. 과정을 작은 문제로 구성하고 재귀적으로 해결한다.

간단한 예시

[7, 1, 5, 2]
[7, 1] | [5, 2]
[7] | [1] [5] | [2]
[1, 7] | [2, 5]
[1, 2, 5, 7]

자바스크립트로 구현

// 배열을 반으로 나누고, 재귀적으로 병합한다.
function mergeSort(arr) {
  // 재귀함수 탈출조건 단일 요소로 구성된 배열이라면, 리턴
  if (arr.length === 1) {
    return arr;
  }
  
  const middle = Math.floor(arr.length / 2); // 배열의 중간 값
  const left = arr.slice(0, middle); // left side items
  const right = arr.slice(middle); // right side items

  return merge(mergeSort(left), mergeSort(right));
}

// 배열을 비교하고, 연결된 결과를 리턴한다.
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // left items와 right items 비교
  while(leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return [...result, ...left.slice(leftIndex), ...right.slice(rightIndex)];
}

const list = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3];
console.log(mergeSort(list)); // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]