ZeroCho Blog

안녕하세요. 이번 시간에는 합병 정렬(머지 정렬 또는 병합 정렬)에 대해 알아보겠습니다. 삽입 정렬보다는 더 복잡하지만, 성능은 훨씬 좋아 자주 쓰이는 정렬 방법 중 하나입니다. 

합병 정렬은 O(NlogN)이기 때문에 성능이 준수합니다. 다만 30개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이도 없고, 정렬하는데 추가적인 메모리가 필요하다는 단점이 있습니다. 보통은 재귀 함수를 사용해서 만듭니다. 삽입 정렬보다 훨씬 더 어렵고 헷갈리니 차분히 따라오세요.

합병 정렬은 분할 정복 알고리즘에 속합니다. 유명한 수학자 폰 노이만이 개발했죠. 분할 정복이란 어떤 문제를 그대로 해결할 수 없을 때, 작은 문제로 분할해서 푸는 방법을 말합니다. 합병 정렬은 배열을 두 개로 나누고, 나눈 것을 다시 두 개로 계속 나눠 정렬합니다. 어떻게 나누기만 하는데 정렬이 되냐고요? 당연히 정렬이 안 되죠. 중간에 어떤 과정을 넣어주어야 합니다. 같이 볼까요?

일단 정렬이 안 된 배열이 있습니다. 그리고 결과를 저장할 빈 배열이 있습니다.
[2,4,5,7,1,3,6,8], [결과배열]
이 배열을 반으로 쪼갭니다.
[2,4,5,7],[1,3,6,8],[]
이제 두 배열의 제일 앞 수를 비교해 작은 숫자를 결과 배열에 넣어줍니다.
[2,4,5,7],[3,6,8],[1]
[4,5,7],[3,6,8],[1,2]
[4,5,7],[6,8],[1,2,3]
[5,7],[6,8],[1,2,3,4]
... 계속 반복합니다. 결국 다음과 같이 됩니다.
[], [], [1,2,3,4,5,6,7,8]
정렬이 완료되었습니다.

뭔가 당황스럽죠? 너무 쉽게 끝난 것 같습니다. 아직 재귀는 사용하지도 않았습니다. 그런데 눈치채셨나요? 처음에 반으로 쪼갤 때, [2,4,5,7], [1,3,6,8]은 이미 정렬되어 있습니다. 항상 이렇게 정렬되어 있지는 않겠죠? 예를 들면 [5,2,4,7,6,1,3,8]를 반으로 쪼개면 [5,2,4,7], [6,1,3,8]이 되는데 이렇게 되면 두 배열의 제일 앞 수끼리 비교해서 넣어도 정렬이 안 되니까요. 위의 것을 앞에서 한 방식으로 정렬한 결과는 [5,2,4,6,1,3,7,8]입니다. 망했죠?

바로 여기서 재귀와 분할 정복이 사용됩니다. 이런 경우는 한 번에 해결할 수 없으니까 작은 문제로 쪼개서 생각합니다. 작은 문제로 쪼개는 것은 재귀를 사용하고요. 즉 아까 [5,2,4,7]과 [6,1,3,8]에 다시 합병 정렬을 실행해주는 겁니다. [5,2,4,7]은 [5,2]와 [4,7]로, [6,1,3,8]은 [6,1]과 [3,8]로 나누어 정렬을 실행합니다.

여기에서도 문제가 한 번 더 발생합니다. [5,2]랑 [6,1]은 아직 정렬이 안 된 상태입니다. [5,2]도 [5]와 [2]로 다시 나누어 실행해줍니다. [5],[2]는 정렬하면 [2,5]가 되고, [4,7]은 그대로, [6],[1]은 [1,6]으로, [3,8]은 그대로 정렬됩니다. 이제 최소 단위로는 다 정렬되었으니 [2,5], [4,7]을 정렬하고, [1,6],[3,8]을 정렬하면 됩니다.

결국에는 [5,2,4,7]과 [6,1,3,8]이 각각 [2,4,5,7], [1,3,6,8]로 바뀌겠죠? 이걸 아까처럼 최종적으로 정렬하면 됩니다. 이해가 되셨나요? 이렇게 반복적으로 쪼개서 마지막에 합치는 게 합병 정렬입니다. 배열 원소의 개수가 홀수여도 상관없습니다. 대충 반으로 쪼개서 앞 두 수끼리 비교하면 되거든요. 코드로 볼까요? 크게 재귀를 하는 부분(mergeSort)과, 앞의 두 수끼리 비교(merge)하는 부분입니다.

var mergeSort = function(array) {
  if (array.length < 2) return array; // 원소가 하나일 때는 그대로 내보냅니다.
  var pivot = Math.floor(array.length / 2); // 대략 반으로 쪼개는 코드
  var left = array.slice(0, pivot); // 쪼갠 왼쪽
  var right = array.slice(pivot, array.length); // 쪼갠 오른쪽
  return merge(mergeSort(left), mergeSort(right)); // 재귀적으로 쪼개고 합칩니다.
}
function merge(left, right) {
  var 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;
};

mergeSort([5,2,4,7,6,1,3,8]); // [1, 2, 3, 4, 5, 6, 7, 8]

숫자가 8개밖에 안 되는데 살짝 느린 감이 있네요. 제 컴퓨터가 낡아서 그렇습니다... 더 많은 숫자를 넣어 정렬해보세요! 컴퓨터가 어디까지 버티나 테스트해보자고요. 참고로 자바스크립트의 배열은 정말 편리합니다. 저 shift 메소드가 얼마나 편리한 건지 다른 언어(특히 C라든가...)도 사용하신다면 뼈저리게 느끼실 겁니다.

mergeSort의 단점은 array 외에도 result라는 추가적인 저장 공간이 필요하다는 겁니다. array의 크기가 커질수록 result의 크기도 커지겠죠. 메모리가 싸진 요즘 같은 경우는 큰 문제가 안 되지만, 수백만 개의 데이터를 처리하는 경우는 문제가 될 수도 있습니다. 앞으로 정렬 방법을 보실 때는 O()가 뭔지도 중요하지만 return 값이 array인지 새로운 배열 result인지도 중요합니다. 새로운 배열을 return한다는 것은 그만큼 메모리를 더 잡아먹는다는 뜻이니까요.

참고로 일부 브라우저에서는 배열.sort()를 할 때 합병 정렬을 사용한다네요. 이번 시간은 많이 어려웠으니까 다음 시간에는 쉬운 버블 정렬에 대해 알아보겠습니다!