|머지정렬 개념 | 머지정렬 알고리즘| 머지정렬 분석 |

■ 머지 정렬 방법

• 머지 정렬은 전형적인 분할 정복 방법의 예
  분할 정복 방법은 순환적으로 문제를 푸는 방법으로서 주어진 문제를 여러 개의 소문제로 분할하여 이 소문제를 순환적으로 푼 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방식

• 즉, 순환 호출시 마다 다음과 같은 세 단계의 작업이 이루어짐

▷ 분할 : 주어진 문제를 여러 개의 소문제로 분할한다.

▷ 정복 : 소문제들을 순환적으로 처리하여 정복한다.
              만약 소문제의 크기가 충분히 작다면 순환 호출없이 소문제에 대한 해가 구해진다.

▷ 합병 : 소문제에 대한 해를 합병하여 원래 문제의 해를 구한다.

• 머지 정렬 알고리즘을 분할 정복 방법의 세 단계로 대응 시켜 보면 다음과 같음

① 분할 : 정렬할 n원소의 배열을 n/2 원소의 두 부분배열로 분할한다.

② 정복 : 두 부분배열에 머지 정렬을 각각 순환적으로 적용하여 두 부분배열을 정렬한다.

③ 합병 : 두 정렬된 부분배열을 머지하여 원래의 정렬된 배열을 만든다.