병합 정렬

 1단계 분할(Divide)

 해결이 용이한 단계까지 문제를 분할해 나간다.

 2단계 정복(Conquer)

 해결이 용이한 수준까지 분할된 문제를 해결한다.

 3단계 결합(Combine)

 분할해서 해결한 결과를 결합하여 마무리한다.

​

 비교 연산 횟수

 MergeTwoArea 함수에서의 비교 연산 : O(n)

 단계의 수 : O(log2n)

 MergeTwoArea 함수를 각 단계마다 호출하므로 전체는… :

O(nlog2n)

 이동 연산 횟수

 각 단계마다…

 임시 배열에 데이터를 병합할 때 n회

 임시 배열에서 원위치로 옮길 때 n회

 단계의 수 : O(log2n)

 전체는 2nlog2n 이므로 O(nlog2n)

 병합 정렬의 단점

 전체 데이터를 담을 임시 메모리 필요