병합 정렬 (Merge Sort)

병합 정렬

병합 정렬은 1) 분할 정복 알고리즘의 하나로, 중복된 수의 입력된 순서와 정렬된 순서가 같은 안정 정렬입니다.

 

1) 분할 정복

분할 정복은 문제를 2개의 문제로 분리하여 각각 해결하고, 결과를 모아 원래의 문제를 해결하는 전략입니다. 

 

https://visualgo.net/en/sorting

 

병합 정렬은 하나의 배열을 두 개의 배열로 분할하고, 분할된 배열을 정렬한 후, 정렬된 두 개의 배열을 다시 결합하는 방식으로 정렬합니다.

 

병합 정렬은 다음과 같은 세가지 과정으로 진행됩니다.

• 분할(Divide) : 배열을 동일한 크기의 배열 2개로 분할한다.
• 정복(Conquer) : 분할된 배열을 조건에 맞게 정렬한다. 분할된 배열의 크기가 충분히 작지 않으면 재귀 호출로 다시 분할 정복 과정을 거친다. 
• 결합(Combine) : 정렬된 배열들을 다시 결합한다.

 

시간 복잡도

병합 정렬의 시간 복잡도는 예를들어 설명하겠습니다.

만약, 데이터가 8개 일 경우, 중간 값이 피벗으로 선택되면 8개, 4개, 2개, 1개 순으로 3번에 걸쳐 데이터가 분할됩니다. 이는 n개의 데이터가 1개로 분할되기까지 $\log{n}$으로 표현할 수 있습니다. 분할의 횟수는 $\log{n}$이고, 분할될 때마다 각각 n번의 비교 연산이 이루어져 최선의 경우는 $O(n\log{n})$의 시간 복잡도를 가집니다.

 

자바스크립트 코드

function mergeSort(arr){
  if(arr.length < 2){
    return arr;
  }
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid, arr.lenght);
  
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
  let result = [];
  
  while(left.length && right.length){
    if(left[0] <= right[0]){
      result.push(left.shift());
    }
    else {
      result.push(right.shift());
    }
  }
  while(left.length){
    result.push(left.shift());
  }
  while(right.length){
    result.push(right.shift());
  }
  return result;
}

console.log(mergeSort([13, 1, 3, 7, 9, 11, 5]));

 

장점

• 최선의 경우와 최악의 경우 모두 $O(n\log{n})$으로 입력 데이터에 영향을 덜 받는 알고리즘입니다.

단점

• 제자리 정렬이 아니기 때문에 별도의 메모리 공간이 필요합니다.
• 데이터의 양이 클 경우, 이동횟수도 많아지므로 시간의 낭비가 커집니다.

 

정리

병합 정렬은 퀵 정렬과 비교하여 많이 설명되는 정렬입니다. 병합 정렬을 이해한다면, 이후 퀵 정렬을 이해하시는데 도움이 될 것입니다. 병합 정렬의 분할, 정복 결합의 과정을 이해하고 넘어가시면 좋을 것 같습니다. : >