C++로 구현하는 3-Way 병합 정렬(Merge Sort) 완벽 가이드

병합 정렬(Merge Sort)은 배열을 재귀적으로 두 부분으로 나눈 뒤 각각을 정렬하고, 마지막에 하나로 합치는 대표적인 분할 정복(Divide and Conquer) 알고리즘입니다. 그 변형인 3-way 병합 정렬(3-way Merge Sort)은 배열을 두 부분이 아닌 세 부분으로 나눈다는 점에서 차별화됩니다.

일반적인 병합 정렬이 배열을 절반 크기의 하위 배열로 계속 쪼개는 방식이라면, 3-way 병합 정렬은 같은 원리로 배열을 1/3 크기의 하위 배열로 나누어 처리합니다.

동작 원리

3-way 병합 정렬은 다음 단계로 진행됩니다.

1. 배열을 저수(low), 중간1(mid1), 중간2(mid2), 고수(high) 기준점을 사용해 세 개의 균등한 구간으로 나눕니다.
2. 세 구간 각각에 대해 재귀적으로 정렬을 수행합니다.
3. 정렬된 세 구간을 한 번에 비교하여 더 작은 값을 순서대로 결과 배열에 병합합니다.

예시

입력 : 46, -1, -44, 79, 31, -41, 11, 20, 74, 94
출력 : -44 -41 -1 11 20 31 46 74 79 94

입력 : 24, -18
출력 : -18 24

시간 복잡도

3-way 병합 정렬의 시간 복잡도는 n·log₃n입니다. 일반 병합 정렬의 n·log₂n보다 로그의 밑이 커지므로 재귀 호출 깊이가 얕아진다는 장점이 있지만, 병합 단계에서 세 구간을 동시에 비교해야 하므로 실질적인 성능 차이는 크지 않습니다.

C++ 구현 코드

// C++ 프로그램: 3-way 병합 정렬 수행
#include <bits/stdc++.h>
using namespace std;

// 세 구간을 하나로 병합하는 함수
void merge(int gArray1[], int low1, int mid1,
           int mid2, int high1, int destArray1[])
{
    int i = low1, j = mid1, k = mid2, l = low1;

    // 세 구간에서 가장 작은 값을 선택
    while ((i < mid1) && (j < mid2) && (k < high1)) {
        if (gArray1[i] < gArray1[j]) {
            if (gArray1[i] < gArray1[k]) {
                destArray1[l++] = gArray1[i++];
            }
            else {
                destArray1[l++] = gArray1[k++];
            }
        }
        else {
            if (gArray1[j] < gArray1[k]) {
                destArray1[l++] = gArray1[j++];
            }
            else {
                destArray1[l++] = gArray1[k++];
            }
        }
    }
    // 남은 두 구간끼리 병합
    while ((i < mid1) && (j < mid2)) {
        if (gArray1[i] < gArray1[j]) {
            destArray1[l++] = gArray1[i++];
        }
        else {
            destArray1[l++] = gArray1[j++];
        }
    }
    while ((j < mid2) && (k < high1)) {
        if (gArray1[j] < gArray1[k]) {
            destArray1[l++] = gArray1[j++];
        }
        else {
            destArray1[l++] = gArray1[k++];
        }
    }
    while ((i < mid1) && (k < high1)) {
        if (gArray1[i] < gArray1[k]) {
            destArray1[l++] = gArray1[i++];
        }
        else {
            destArray1[l++] = gArray1[k++];
        }
    }
    // 각 구간의 남은 요소 복사
    while (i < mid1)
        destArray1[l++] = gArray1[i++];
    while (j < mid2)
        destArray1[l++] = gArray1[j++];
    while (k < high1)
        destArray1[l++] = gArray1[k++];
}

// 재귀적으로 3-way 분할 정렬을 수행하는 함수
void mergeSort3WayRec(int gArray1[], int low1,
                      int high1, int destArray1[])
{
    // 배열 크기가 1 이하이면 종료
    if (high1 - low1 < 2)
        return;

    // 세 구간으로 나누기 위한 중간 지점 계산
    int mid1 = low1 + ((high1 - low1) / 3);
    int mid2 = low1 + 2 * ((high1 - low1) / 3) + 1;

    mergeSort3WayRec(destArray1, low1, mid1, gArray1);
    mergeSort3WayRec(destArray1, mid1, mid2, gArray1);
    mergeSort3WayRec(destArray1, mid2, high1, gArray1);

    // 정렬된 세 구간 병합
    merge(destArray1, low1, mid1, mid2, high1, gArray1);
}

// 3-way 병합 정렬 래퍼 함수
void mergeSort3Way(int gArray1[], int n1)
{
    // 배열이 비어 있으면 종료
    if (n1 == 0)
        return;

    int fArray1[n1];
    for (int i = 0; i < n1; i++)
        fArray1[i] = gArray1[i];

    // 정렬 함수 호출
    mergeSort3WayRec(fArray1, 0, n1, gArray1);

    for (int i = 0; i < n1; i++)
        gArray1[i] = fArray1[i];
}

// 드라이버 코드
int main()
{
    int data1[] = {46, -1, -44, 79, 31,
                   -41, 11, 20, 74, 94};

    mergeSort3Way(data1, 10);

    cout << "After 3 way merge sort: ";
    for (int i = 0; i < 10; i++) {
        cout << data1[i] << " ";
    }
    return 0;
}

실행 결과

After 3 way merge sort: -44 -41 -1 11 20 31 46 74 79 94

마무리

3-way 병합 정렬은 기존 병합 정렬의 분할 개수를 늘린 변형 알고리즘으로, 재귀 트리의 깊이를 줄일 수 있다는 특징이 있습니다. 다만 병합 과정에서 세 구간을 동시에 비교해야 하는 오버헤드가 있으므로, 실무에서는 데이터 특성과 환경에 따라 일반 병합 정렬과 함께 비교 검토한 후 적용하는 것이 좋습니다.