[JS] 병합 정렬

1. 병합 정렬

  병합 정렬은 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법을 말한다.

 

  병합 정렬도 퀵 정렬 처럼 분할정복 알고리즘을 이용하는 방법이며,

 

  속도 또한 퀵 정렬과 같이 $$ O(N\times log_2{N}) $$

  의 성능을 보인다.

 

  병합 정렬이 퀵 정렬과 속도는 같지만, 퀵 정렬은 최악의 경우 $$ O(N^2) $$

  의 속도를 가지지만,

 

  병합 정렬은 최악의 경우에도 $$ O(N\times log_2{N}) $$

  의 속도를 가지는 매우 안정적인 정렬이라고 할 수 있다.

 

2. 동작 순서

  병합 정렬의 동작 순서는 매우 간단하다.

 

  2개씩 나누어서 분할 한 후 (재귀 함수를 이용)

 

[그림 1] 두 개씩 분할

   

  결합을 하면 되는데, 주의할 점은 결합을 함과 동시에 정렬 작업을 해주어야 한다.

 

[그림 2] 병합 작업

 3. 시간 복잡도

  왜 병합 정렬은 항상 $$ O(N\times log_2{N}) $$

  의 복잡도가 나오는 것일까?

 

  다음 그림을 보자.

 

 

[그림 3] 병합 정렬의 높이 

    

  위 그림은 병합 정렬의 높이를 나타낸 것이다. 빨간색 텍스트는 높이이고, 파란색 N은 덩어리의 너비를 말한다.

 

  N이 1일 때는 높이가 0이 되고,

  N이 2일 때는 높이가 1가 되며,

  N이 4일 때는 높이가 2가 되고,

  N이 8일 때는 높이가 8이 된다.

 

  쉽게 표현하기 위해 N을 너비라고 말했지만, N은 각각의 분할된 배열을 탐색하는 횟수를 말한다. 

 

  이러한 이유로 N과 높이의 관계는 log₂N의 관계가 되며,

 

  가로와 세로의 곱을 곱하면 Nlog₂N이 되므로, 병합 정렬은 최악의 경우에도 

 

  Nlog₂N의 속도를 자랑하게 된다.

 

4. 프로그램 코드

 병합 정렬 코드는 다음과 같다.

const merge = (left, right) => {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while(leftIndex < left.length && rightIndex < right.length){
    if(left[leftIndex] <= right[rightIndex])
      result.push(left[leftIndex++])
    else
      result.push(right[rightIndex++])
  }

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

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

  

5. 참고 자료

1. 동빈나 님의 블로그 - 7. 병합 정렬

2.  자바스크립트로 합병정렬 구현