병합정렬(merge sort)

병합정렬(merge sort)

---

배열을 작은 단위로 분할 → 분할된 배열 정렬 → 이들을 다시 정렬

원리

1. 배열을 작은 단위로 분할
2. 분할된 배열을 정렬
3. 정렬된 배열을 다시 정렬

pseudocode

병합정렬(list, left, right)
	middle = (left+right) / 2 #l과 r의 중간 지점 계산
    정렬(list, left, mid) #전반부 정렬
		정렬(list, mid+1, right) #후반부 정렬
	합치기(list, left, mid, right) #합병

best case 시간복잡도 : $O(n$ $log$ $n)$
avg case 시간복잡도 : $O(n$ $log$ $n)$
worst case 시간복잡도 : $O(n$ $log$ $n)$
동일한 시간복잡도를 가진다 ∵ 무조건 배열을 절반으로 분리
안정성 : 안정
장점 : 초기 데이터의 분산정도에 영향받지X (항상 $O(n$ $log$ $n)$의 시간복잡도를 가진다)
단점 : 분할된 배열을 저장할 추가적인 메모리 필요

실제코드

#include <stdio.h>
# define MAX_SIZE 20
int sorted[MAX_SIZE]; // 추가적인 공간이 필요

void merge(int list[], int left, int mid, int right){
    int i = left;
    int j = mid+1;
    int k = left;
    int l;
    
    while(i<=mid && j<=right){
        //쪼개진 배열 내에서 left인덱스의 값과 mid인덱스 값을 비교 후 크기순으로 sorted에 추가
        if(list[i]<=list[j])
          sorted[k++] = list[i++];
        else
          sorted[k++] = list[j++];
    }
    // 남아 있는 값들을 일괄 복사
      if(i>mid){ //mid기준 뒤쪽(j)이 남은경우
        for(l=j; l<=right; l++)
          sorted[k++] = list[l];
      }
      else{ //mid기준 앞쪽(i)이 남은경우
        for(l=i; l<=mid; l++)
          sorted[k++] = list[l];
      }
    //원래의 배열에 복사
    for(l=left; l<=right; l++){
        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);
      
      // 쪼개진 두 부분을 정렬후 병합
      merge(list, left, mid, right);
  }
}

int main(int argc, const char * argv[]) {
    int arr[20] = {
        3, 5, 2, 2, 4,
        6, 1, 3, 7, 8,
        2, 11, 2, 21, 20,
        12, 14, 1, 6, 16
    };
    int n = sizeof(arr) / sizeof(int);
    merge_sort(arr, 0, n-1);

    // 정렬된 배열 출력
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}