합병 정렬(Merge sort)

: 배열의 크기를 더이상 나눠지지 않은 형태까지 분할하고(Divide), 전부다 합쳐질 때 까지 정렬하며 합친다(Conquer)

• 어떠한 경우에도 O(n logn) 시간 복잡도를 갖는다.(복잡도가 안정적)
• Divide and Conquer 방식
  • 문제를 작은 단위의 문제로 분할하고 각각을 해결(정복)한다음 결합해서 문제를 해결
    • 따라서 합병 단계에서 실제 정렬이 이루어진다.
    • 합병단계에서 추가적인 리스트를 필요로한다.(Array를 통한 구현의 경우)
  • 보통 재귀를 이용
• 안정성 있는 정렬
  • 안정성 있게 하려면, 같은 값이 나왔을 때 첫번째 배열의 원소를 먼저 넣는 방식으로 해야 해결 될 듯

장단점

• 장점
  • 연결 리스트로 구현하면 링크 인덱스만 변경하면 되므로 데이터의 이동은 아주 작아진다.
    • 제자리 정렬로 구현할 수 있다.
    • 모든 정렬 중 가장 효율적일 수 있다고 함.
    • 이 경우 퀵 정렬보다 유리할 수 있다.
• 단점
  • Array로 구현하면 임시 배열이 필요하다(제자리 정렬이 아니다)
  • 레코드 크기가 크면 이동횟수가 많아져 시간낭비가 커진다.
  • 지역성이 떨어진다: 캐시의 Page가 계속 변경된다. 따라서, 퀵 소트에 비해 지역성이 떨어진다. 그러나, 힙 소트에 비해서는 나쁘지 않다고 한다.

시간복잡도

• 분할 단계 - 비교연산, 이동연산 수행 안하고 그냥 분할.
• 병합 단계
  • 호출의 깊이 = O(log N)
  • 비교 연산 갯수 = 각 층에서 최대 O(n)
  • 따라서 O(N logN)
• 이동횟수 = 2n log n
  • 임시 배열에 복사 -> 다시 가져오기 == 2n
  • 순환 호출 == log n

소팅 과정

과정 요약

1. 일단 다 나눈다(재귀를 통해 더이상 못 나눌 때까지)
2. 두 리스트들의 값들을 앞부터 하나씩 비교해, 우선순위를 새로운 리스트로 옮긴다
   • 둘 중 하나 먼저 끝나면 나머지 리스트 남은 부분 전체를 비교 없이 그냥 다 넣어준다.

코드

void merge(int data[], int left, int mid, int right) {
    int lo = left;
    int hi = mid + 1;
    int sortedData[MAX] = {0, };
  
    int idx = lo;
    
    while(lo <= mid && hi <= right)
        sortedData[idx++] = (data[lo] <= data[hi]) ? data[lo++] : data[hi++];
    
    while(lo > mid)
        sortedData[idx++] = data[hi++];
    
    while(hi > right)
        sortedData[idx++] = data[lo++];
    
    while(left <= right) // 원래 리스트에 복사 (다음 sorting을 위해)
        data[left] = sortedData[left++];
}

void mergeSort(int data[], int left, int right) {
    if(left == right) // atomic 원소
        return;
    
    int mid = left + (right - left) / 2;
    mergeSort(data, left, mid); // 분할을 위한 과정
    mergeSort(data, mid + 1, right);
    merge(data, left, mid, right); // 합병을 위한 과정
}

Reference)

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

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html