합병정렬

합병정렬(merge sort)

분할정복법을 이용한 정렬이다.
분할정복법 ?
분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
정복 : 각각의 작은 문제를 순환적으로 해결
합병 : 작은 문제의 해를 합하여(merge) 원래문제에 대한 해를 구함.

1. 데이터가 저장된 배열을 절반으로 나눔
2. 각각을 순환적으로 정렬
3. 정렬된 두 개의 배열을 합쳐 전체를 정

{'A','L','G','O','R','O','T','H','M','S'}

1. {'A','L','G','O','R'} , {'O','T','H','M','S'}
2. {'A','G','L','O','R'}, {'H','I','M','S','T'}
3. {'A','G','H','I','L','M','O','R','S','T'}

{1,2,2,3,4,5,6,7}

1. {2,4,5,7}

   1. {2,5}
      1. {2}. {5}
   2. {4,7}
      1. {4}, {7}

2. {1,2,3,6}

   1. {1,3}

      1. {1},{3}

   2. {2,6}

      1. {2},{6}

         mergeSort(A[], p, r) -> A[p...r]을 정렬한다.
         {
         if(p < r) then 
         {
         q <- (p+r) / 2  -----> 1. p, r의 중간 지점 계산
         mergeSort(A, p, q); -----> 2. 전반부 정렬
         mergeSort(A, q+1, r); ----> 3. 후반부 정렬
         merge(A, p, q, r); ------> 4. 합병
         }
         }

         merge(A[], p, q, r)
         {
         정렬되어있는 두 배열 A[p...q]와 A[q+1...r] 을 합하여
         정렬된 하나의 배열 A[p...r]을 만든다.
         }

         void merge(int data[], int p, int q, int r) {
         int i = p; j = q+1, k=p
         int temp[data.length()];
         while( i<=q && j<=r ) {
         if(data[i]<=data[j])
          temp[k++] = data[i++];
         else
          temp[k++] = data[j++];
         }
         

while(i <= q)  
    temp[k++] = data[i++];  
while(j <= r)  
    temp[k++] = data[j++];  
for(int i = p; i <= r; i++)  
    data[i] = temp[i];  
}