[알고리즘] 병합 정렬(Merge Sort)

배열을 앞부분과 뒷부분으로 나누어 각각 정렬(병합정렬 재귀)한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘.

코드 1 (배열공유 X)

 // 내가 만든 merge_sort
 void merge_sort(int a[], int n, int c[]) {
     
     int mid = (n - 1) / 2;
     
     if(n >= 2) {
         merge_sort(a, mid + 1, c);
         merge_sort(a + mid + 1, n -(mid + 1), c);
                 
         int pa = 0, pb = mid + 1, pc = 0;
         
         while(pa <= mid && pb <= n - 1) {
             a[pa] <= a[pb] ? (c[pc++]=a[pa++]):(c[pc++]=a[pb++]);
         }
         while(pa<=mid)
             c[pc++] = a[pa++];
         while(pb<=n-1)
             c[pc++] = a[pb++];
         
         for(int x = 0; x < n ; x++) {
             a[x] = c[x];
         }
         //free(c);
     }
 }

 

코드 2 (배열공유)

 static int *buff;

 void __merge_sort(int a[], int left, int right) {
     if(left < right) {
         int p = 0; //buff에서 쓰임.
         int i;
         int j = 0; //buff에서 쓰임.
         int k = left;
         int center = (left + right) / 2;
         
         __merge_sort(a, left, center);
         __merge_sort(a, center+1, right);
         
         for(i = left; i <= center; i++) {
             buff[p++] = a[i];
         }
         
         while(i <= right && j < p) {
             a[k++] = (buff[j] <= a[i])?buff[j++]:a[i++];
         }
         
         while(j < p) {
             a[k++] = buff[j++];
         }
     }
 }

 int merge_sort(int a[], int n) {
     if((buff=calloc(n, sizeof(int))) == NULL)
        return -1;
     __merge_sort(a, 0, n - 1);
     free(buff);
     return 0;
 }

 

병합 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이다. 
(서로 교환안하니까 안정적이라고생각하면될듯)

병합 정렬의 시간복잡도 : O(n log n)