병합정렬/합병정렬(Merge Sort)

병합정렬/합병정렬(Merge Sort)는 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈 다음 정렬해서 병합한다. 즉, 원래의 정렬 문제와 성격이 똑같고 단지 크기만 반으로 줄었을 뿐이다. 후반부에 대한 정렬도 마찬가지다. 병합정렬은 자신에 비해 크기가 반인 문제를 두개 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다.

위 그림의 예를 살펴보면 초기 배열 A = { 5, 2, 4, 7, 1, 3, 2, 6} 이다. 병합정렬의 전반부, 후반부 정렬이 재귀적으로 반복되면서 배열의 원소가 하나씩 남을때 까지 쪼개진다. 그리고 각각 병합을 하면서 정렬이 이루어진다. {5}, {2} 가 병합되어 {2, 5} 가 되고 {4}, {7} 이 병합되어 {4, 7} ... 이렇게 진행되고 다음 스테이지에서 {2, 5} , {4, 7}이 병합되어 {2, 4, 5, 7} 이 되고 {1, 3}, {2, 6}이 병합되어 {1, 2, 3, 6}이 된다. 그 다음 스테이지에서 {2, 4, 5, 7} 과 {1, 2, 3, 6}이 병합되어 최종적으로 정렬된 {1, 2, 2, 3, 4, 5, 6, 7} 이 된다.

병합정렬(Merge Sort)의 슈도코드는 다음과 같다.

위의 함수 merge()를 좀더 구체적으로 기술하면 다음과 같다.