합병 정렬

합병 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘 중 하나로, 큰 문제를 작은 문제로 분할하여 각각을 해결한 후, 결과를 모아서 원래의 문제를 해결하는 알고리즘입니다. 이 알고리즘은 일반적으로 재귀적인 방법을 사용하여 구현하며, 다음과 같은 과정을 거칩니다. 주어진 배열을 두 부분으로 나눕니다. 이때, 중간 지점을 기준으로 나누는 것이 일반적입니다. 각각의 부분 배열을 재귀적으로 머지 정렬합니다. 두 개의 정렬된 부분 배열을 병합하여 하나의 정렬된 배열로 만듭니다.

 

void merge(int list[], int left, int mid, int right) {
    int sorted[SIZE]; // 임시 배열
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    // 분할 정렬된 list의 합병
    while (i <= mid && j <= right) {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }

    // 남아 있는 값들을 일괄 복사
    if (i > mid) {
        for (l = j; l <= right; l++)
            sorted[k++] = list[l];
    } else {
        for (l = i; l <= mid; l++)
            sorted[k++] = list[l];
    }

    // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
    for (l = left; l <= right; l++) {
        list[l] = sorted[l];
    }
}

void merge_sort(int list[], int left, int right) {
    int mid;

    if (left < right) {
        mid = (left + right) / 2; // 중간 위치를 계산하여 리스트를 균등 분할

        // 앞쪽 부분 리스트 정렬 - Divide and Conquer
        merge_sort(list, left, mid);

        // 뒤쪽 부분 리스트 정렬 - Divide and Conquer
        merge_sort(list, mid + 1, right);

        // 정렬된 2개의 부분 배열을 합병하는 과정 - Combine
        merge(list, left, mid, right);
    }
}

 

시간 복잡도

머지 정렬은 분할 정복 알고리즘의 대표적인 예시로, 입력 크기가 n일 때, n개의 원소를 2개씩 분할하고, 2개의 리스트를 병합하는 단계를 log(n)번 반복합니다. 따라서, 전체 시간 복잡도는 O(n log n)입니다.

 

공간 복잡도

입력 리스트와 같은 크기의 보조 배열이 필요합니다. 따라서, 전체 공간 복잡도는 O(n)입니다.