Merging Sort   병합 정렬

1. 병합 정렬 (Merging Sort)

  ㅇ 자료를, 부분 집합으로 나누고, 이를 병합하면서, 정렬하는 방식
     - 정렬 대상을 2개(거의 같은 크기)로 분할해가면서, 더이상 분할되지 않으면,
       분할된 그룹들을 병합해가며 정렬 함
     - 즉, 배열을 이등분한 다음, 각각을 재귀적으로 병합하여 정렬 함 

  ㅇ 1945년 존 폰 노이만이 고안함

  ㅇ 계산 효율성 : O(nlogn)

  ㅇ 특징
     - 명시적으로 재귀 호출을 사용
     - 퀵 정렬 처럼 분할 정복 전략을 사용
     - 안정 정렬
     - 고른 성능을 보임

  ㅇ 알고리즘 표현 例
     
mergeSort(Data[],p,r) {
    q = (p+r)/2;            // 이등분
    mergeSort(Data[],p,q)   // 전반부 정렬 (재귀호출)
    mergeSort(Data[],q+1,r) // 후반부 정렬 (재귀호출)
    merge(Data[],p,q,r)     // 병합
}

merge(Data[],p,q,r) {
    // 정렬된 두 부분 배열을 합쳐 하나의 큰 배열을 만들어 반환하는 루틴
}