개요
폰 노인만에 의해서 개발된 Merge Sort 는 안정적으로 nlogn 만에 배열을 정렬할 수 있도록 해준다. 기본 원리는 배열을 일단 최소 단위까지 쪼갠후 최소 단위부터 조금씩 맏추면서 올라가는 방식이다. 분할 정복 알고리즘의 좋은 예시이다. 성능은 퀵 정렬보다 전반적으로 뒤떨어지고, 데이터 크기만한 메모리가 더 필요하지만 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다는 점이다. 힙이나 퀵의 경우에는 배열 A[25]=100, A[33]=100인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있다. 그에 반해서 병합정렬은 그런 거 없다. 정렬되어 있는 두 배열을 합집합할 때 이 알고리즘의 마지막 단계만을 이용하면 가장 빠르게 정렬된 상태로 합칠 수 있다.
알고리즘
합병 정렬은 다음과 같이 작동한다.
- 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
- 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
- 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.