합병 정렬

• 두개의 정렬된 리스트를 하나의 정렬된 리스트로 합병

반복 합병 정렬(Iterative Merge Sort)

• 입력 리스트를 길이가 1인 n개의 정렬된 서브리스트로 간주

• 반복 합병 정렬 단계
  • 첫번째 합병 단계 : 리스트들을 쌍으로 합병하여 크기가 2인 n/2개의 리스트를 얻는다
    • n이 홀수면 리스트 하나는 크기가 1
  • 두번째 합병 단계 : n/2개의 리스트를 다시 쌍으로 합병하여 n/4개의 리스트를 얻는다
  • 합병 단계는 하나의 서브 리스트가 남을 때까지 계속된다
    • 한번 합병할 때마다 서브 리스트의 수는 반으로 줄어든다
      

ex)

입력 리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)

순환 합병 정렬 (Recursive Merge Sort)

• 정렬할 리스트를 거의 똑같이 두 개로 나눈다
  • left 서브리스트와 right 서브리스트
• 서브리스트들은 순환적으로 정렬
• 정렬된 서브리스트들은 합병된다

ex)
입력 리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 49, 19)

순환적 합병 정렬의 서브 리스트 분할

• 두 개의 서브리스트를 만든다
  • left ~ [(left+right)/2], [(left+right)/2]+1 ~ right
• 정수 배열 link[1:n]을 사용
  • 함수 merge가 사용될 때 일어나는 레코드 복사를 피하기 위해 정수 포인터를 각 레코드에 연관시키기 위함
  • list[i] - 정렬된 서브리스트에서 레코드 I 다음에 있는 레코드
  • 이 배열의 사용으로 레코드 복사는 링크 변경으로 대체되고 정렬 함수의 실행 시간은 레코드 크기 s에 독립적이 됨
  • 필요한 추가 공간 : O(n)
  • 최종 체인이 결정하는 정렬 순서로 레코드들을 물리적으로 재정돈해야하는 후처리 필요
  • 연산시간 : O(nlogn)

mergeSort 분석

• 합병의 각 단계에 걸리는 시간 : O(n)
• 총 연산 시간 : O(nlogn)
• 최악의 경우에 가장 좋은 방법. 히프 정렬에 비해 더 많은 공간을 필요로 함

구현

public class Main {
    public static int[] src;
    public static int[] tmp;

    public static void main(String[] args) {
        src = new int[]{26, 5, 77, 1, 61, 11, 59, 15, 48, 19};
        tmp = new int[src.length]; printArray(src);
        mergeSort(0, src.length-1); printArray(src);
    }

    public static void mergeSort(int start, int end) {
        if (start<end) {
            int mid = (start+end) / 2;
            mergeSort(start, mid);
            mergeSort(mid+1, end);
            int p = start;
            int q = mid + 1;
            int idx = p;

            while (p<=mid || q<=end) {
                if (q>end || (p<=mid && src[p]<src[q])) {
                    tmp[idx++] = src[p++];
                } else {
                    tmp[idx++] = src[q++];
                }
            }

            for (int i=start;i<=end;i++) {
                src[i]=tmp[i];
            }
        }
    }

    public static void printArray(int[] a) {
        for (int i=0;i<a.length;i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

---

reference

• 고려대학교 김상곤 교수님 강의 중
• [알고리즘] Java로 구현하는 쉬운 Merge Sort (병합 정렬, 합병 정렬)