Merge sort (병합 정렬)

병합 정렬

    -  분할 정복 알고리즘으로 정렬하려는 배열을 균등하게 분할하여 정렬

 

 

 

동작

    - 정렬할 배열을 균등하게 분할하고

    - 분할된 부분 배열을 정렬하고

    - 두 개의 정렬된 부분 배열을 병합하여 전체를 정렬

 

  - 예시 : 애니메이션

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

    - 예시 : 전체 과정 예시

 

    - 예시 : 추가 배열이 필요한 이유 (마지막 정복 결합을 예시로)

 

 

 

 

구현

// 정렬과 병합하는 함수  
void merge(int list[], int left, int mid, int right){
 
 // i : 정렬된 왼쪽 배열의 인덱스
    // j : 정렬된 오른쪽 배열의 인데스
    // k : 새롭게 정렬할 배열의 인덱스
   int i, j, k, t;
i = left;
   j = mid+1;
   k = left;
 
   // 왼쪽과 오른쪽 배열의 요소를 비교하면서 새로운 배열에 저장  
    while(i<=mid && j<=right){
        if(list[i]<=list[j])
            sorted[k++] = list[i++];
        else
           sorted[k++] = list[j++];
   }
 
   // 왼쪽 배열은 끝났지만 오른쪽 배열은 남아 있을 때
 // 오른쪽 배열의 나머지를 새로운 배열에 저장  
   if(i>mid){
   for(t=j; t<=right; t++)
        sorted[k++] = list[t];
   }
      
    // 오른쪽 배열은 끝났지만 왼쪽 배열은 남아 있을 때 
    // 왼쪽 배열의 나머지를 새로운 배열에 저장  
   else{
        for(t=i; t<=mid; t++)
           sorted[k++] = list[t];
   }
 
    // 새로운 배열에 저장되었던 값을 원래 배열에 옮기기  
   for(t=left; t<=right; t++){
        list[l] = sorted[l];
   }
      
}
 
 
// 합병 정렬
void merge_sort(int list[], int left, int right){
   int mid;
 
   if(left<right){
       // 균등하게 나누기 위해 가운데 값 구함  
        mid = (left+right)/2
    
        // 가운데를 기준으로 왼쪽 배열을 다시 나누기  
        merge_sort(list, left, mid);
    
        // 가운데를 기준으로 오른쪽 배열 다시 나누기  
        merge_sort(list, mid+1, right);
    
        // 2개의 정렬된 부분 배열을 정렬하고 합치기  
        merge(list, left, mid, right);
   }
}

 

 

 

특징

    - 안정 정렬

    - 데이터의 분포에 상관 없이 시간복잡도 O(N * logN)

        * 균등한 크기로 부분 배열을 나누기 때문

    - 시간 복잡도 : O(N * logN)

    - 배열을 저장할 추가 배열 필요

 

 

 

참고

    - 블로그 1

    - 블로그 2

    - 블로그 3

    - 위키피디아 1