병합 정렬

개념

분할정복 개념이 들어간 정렬 알고리즘입니다.

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다.

퀵 정렬과 동일하게 순환호출을 통해서 구현합니다.

 

1. 배열의 길이가 0 또는 1이면 이미 정렬된 것으로 봅니다. Base Case입니다.
2. 배열의 길이가 2 이상인 경우에 정렬되지 않은 배열로 절반으로 잘라 두 서브 배열로 나눕니다.
3. 각 서브 배열을 재귀적으로 합병하여 정렬합니다.
4. 두 부분 배열을 다시 하나의 정렬된 배열로 합병합니다.

합병 정렬을 분할정복개념으로 나누면 아래와 같습니다.

• Divide: 입력 배열을 같은 크기의 2개로 나눈다.
• Conquer: 부분 배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면(base case) 순환호출을 통해 다시 분할한다.
• Combine: 정렬된 배열들을 합친다.

 

합병정렬시에는 기존 초기배열의 크기만큼의 추가적인 리스트가 필요합니다.

각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용합니다.

 

 

코드 구현

void merge(vector<int> &arr, int left, int mid, int right) {
    vector<int> tmp;

    int x = left;
    int y = mid + 1;
    while (x < mid + 1 && y <= right) {
        int v1 = arr[x];
        int v2 = arr[y];

        if (v1 > v2) {
            tmp.push_back(v2);
            y++;
        } else {
            tmp.push_back(v1);
            x++;
        }
    }
    if (x < mid + 1) {
        for (int i = x; i < mid + 1; i++) {
            tmp.push_back(arr[i]);
        }
    } else {
        for (int i = y; i < right + 1; i++) {
            tmp.push_back(arr[i]);
        }
    }
    int c = 0;
    for(int i = left; i < right+1; i++){
        arr[i] = tmp[c++];
    }
}


void merge_sort(vector<int> &arr, int left, int right) {
    int mid;

    if (left < right) {
        mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

장단점

단점:

• 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
• 제자리 정렬(in-place sorting)이 아니다.
• 레크드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

장점: 

• 안정적인 정렬 방법
• 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
• 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
• 제자리 정렬(in-place sorting)로 구현할 수 있다.
• 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

시간복잡도

 

코드를 보면 알겠지만 분할 단계는 연산이 수행되지 않는다. 

합병단계:

배열의 개수가 2의 거듭제곱이라고 가정하였을 때, 순환호출의 깊이는 k = log2n이 된다. 

각 합병 단계에서의 비교연산은 배열의 길이 만큼 비교를 하고, 값복사를 함으로 2*n이 된다. 이때 상수는 무시하므로 n이 나온다.

 

따라서 최종적인 시간복잡도는 O(n*log2n)이 나온다.