-
합병정렬 본문
이번 시간에는 합병 정렬(머지 정렬 또는 병합 정렬)에 대해 알아보겠습니다.
삽입 정렬보다는 더 복잡하지만, 성능은 훨씬 좋아 자주 쓰이는 정렬 방법 중 하나입니다.
합병 정렬은 O(NlogN)이기 때문에 성능이 준수합니다. 다만 30개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이도 없고, 정렬하는데 추가적인 메모리가 필요하다는 단점이 있습니다. 보통은 재귀 함수를 사용해서 만듭니다. 삽입 정렬보다 훨씬 더 어렵고 헷갈리니 차분히 따라오세요.
합병 정렬은 분할 정복 알고리즘에 속합니다. 유명한 수학자 폰 노이만이 개발했죠. 분할 정복이란 어떤 문제를 그대로 해결할 수 없을 때, 작은 문제로 분할해서 푸는 방법을 말합니다. 이것을 우리는 Divide and Conquer라고도 부릅니다.
합병 정렬은 배열을 두 개로 나누고, 나눈 것을 다시 두 개로 계속 나눠 정렬합니다. 여기에는 pivot이라는 개념이 도입되는데, 배열에서 중간값을 pivot이라고 지정하여 그 숫자보다 작은건 왼쪽으로, 큰건 오른쪽으로 오게끔 정렬할 수 있습니다.
일단 정렬이 안 된 배열이 있습니다.
그리고 결과를 저장할 빈 배열이 있습니다.
[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)하는 부분입니다.
int mergeSort(array) {
if (array.length < 2) return array; // 원소가 하나일 때는 그대로 내보냅니다.
if(p<q){
int pivot = (p+q)/2; // 대략 반으로 쪼개는 코드
int left = MergeSort(array,p,pivot); // 쪼갠 왼쪽
int right = MergeSort(array,pivot+1,q); // 쪼갠 오른쪽
return merge(mergeSort(left), mergeSort(right)); // 재귀적으로 쪼개고 합칩니다.
}
function merge(left, right) {
int result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) { // 두 배열의 첫 원소를 비교하여
result.put(left.shift()); // 더 작은 수를 결과에 넣어줍니다.
} else {
result.put(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]
mergeSort의 단점은 array 외에도 result라는 추가적인 저장 공간이 필요하다는 겁니다. array의 크기가 커질수록 result의 크기도 커지겠죠. 메모리가 싸진 요즘 같은 경우는 큰 문제가 안 되지만, 수백만 개의 데이터를 처리하는 경우는 문제가 될 수도 있습니다. 앞으로 정렬 방법을 보실 때는 O()가 뭔지도 중요하지만 return 값이 array인지 새로운 배열 result인지도 중요합니다. 새로운 배열을 return한다는 것은 그만큼 메모리를 더 잡아먹는다는 뜻이니까요.
참고로 일부 브라우저에서는 배열.sort()를 할 때 합병 정렬을 사용한다네요.