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

병합정렬(Merge Sort)

• 선택, 버블, 삽입 정렬보다 빠른 알고리즘
• Divide and Conquer 전략을 활용하는 알고리즘
• 분할 할 때, 배열이 절반으로 줄어들어 시간 복잡도는 O(logN)
• 합병 할 때, 모든 값을 비교해야 하기 때문에 시간 복잡도는 O(N)
• 두 개의 배열을 병합할 때 병합 결과를 담을 배열이 추가적으로 필요 (Space complexity: Not in-place)
• 최악의 경우 O(nlogn)인 알고리즘
• 재귀에 대한 이해가 있어야 한다.

코드 설계

• 하나의 큰 문제를 두 개의 작은 문제로 분할
• 더 이상 나눌 수 없을 때 병합
• 병합 시 정렬을 하면서 병합하여 정렬을 완성

0: 2 4 1 6 8 5 3 7

1: 2 4 1 6        8 5 3 7

2: 2 4        ||        1 6        ||        8 5        ||        3 7

3: 2    ||    4    ||    1    ||    6    ||    8    ||    5    ||    3    ||    7

4: 2 4        ||        1 6        ||        5 8     ||        3 7

5: 1 2 4 6        ||        3 5 7 8

6: 1 2 3 4 5 6 7 8

• pseudo-code

Merge(L, R, A) {
    nL <- length(L)
    nR <- length(R)
    i <- 0, j <- 0, k <- 0
    while(i < nL && j < nR) {
        if( L[i] <= R[j] ) {
            A[k] <- L[i]
            i <- i + 1
        } else {
            A[k] <- R[j]
            j <- j + 1
        }
        k <- k + 1
    }
    while(i < nL) {
        A[k] <- L[i]
        i <- i + 1
        k <- k + 1
    }
    while(j < nR) {
        A[k] <- R[j]
        j <- j + 1
        k <- k + 1
    }
}    
MergeSort(A) {    
    n <- length(A)
    // 기저조건: 더 이상 나눌 수 없는 배열의 길이인 경우
    if (n < 2) return
    mid <- n / 2

    left <- array.size(mid)
    right <- array.size(n - mid)

    for i <- 0 to mid - 1
        left[i] <- A[i]
    for i <- mid to n - 1
        right[i - mid] <- A[i]

    MergeSort(left)
    MergeSort(right)
    Merge(left, right, A)    
}

코드 구현

    public void mergeSort(int[] A) {
        int n = A.length;
        if (n < 2) return; // 배열의 요소가 1개인 경우 리턴

        int mid = n / 2; // 배열의 중간 요소

        int[] left = new int[mid]; // 좌측 배열
        int[] right = new int[n - mid]; // 우측 배열

        for (int i = 0; i < mid; i++) {
            left[i] = A[i];
        }
        for (int i = mid; i < n; i++) {
            right[i - mid] = A[i];
        }
        mergeSort(left);
        mergeSort(right);
        merge(left, right, A);
    }

    private void merge(int[] L, int[] R, int[] A) {
        int nL = L.length;
        int nR = R.length;

        int i = 0 , j = 0 , k = 0;

        while(i < nL && j < nR) {
            if(L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
            k++;
        }
        while(i < nL) { // L 배열에 A에 넣지 않은 여분이 있는 경우 
            A[k] = L[i];
            i++;
            k++;
        }
        while(j < nR) { // R 배열에 A에 넣지 않은 여분이 있는 경우 
            A[k] = R[j];
            j++;
            k++;
        }
        // 과정 출력
    }

• 과정 출력 (병합되는 과정에 출력)

2    4    
1    6    
1    2    4    6    
5    8    
3    7    
3    5    7    8    
1    2    3    4    5    6    7    8    

분석

• 복잡도 분석
  • 순환 호출의 깊이: k = logN
  • 각 합병 단계의 비교 연산: 최대 N번
  • 순환 호출의 깊이 만큼 합병 단계 * 각 합병 단계의 비교연산: O(N * logN)
• 공간 복잡도
  • 공간의 소비는 목록의 요소의 수에 비례한다.