합병정렬 (in BSSM)

황준혁·2024년 11월 5일

Special Thanks to @hanjiwon1108

특징

합병 정렬은 분할 정복(Divide and Conquer) 기반의 알고리즘으로, 데이터의 정렬 여부와 관계없이 O(n log n)의 시간 복잡도를 유지합니다.

동작 원리

분할 (Divide): 입력 배열을 두 개로 나누며, 배열의 크기가 1이 될 때까지 반복합니다.
정복 (Conquer): 나누어진 배열을 각각 정렬합니다.
결합 (Combine): 정렬된 부분 배열들을 비교하며 병합합니다.

시간 및 공간 복잡도

시간 복잡도: 항상 O(n log n)을 유지합니다.
공간 복잡도: 추가적인 배열 사용으로 O(n)의 공간 복잡도를 가집니다.

수행 과정

분할: 배열을 반으로 나눕니다.
정복: 길이가 1인 배열은 이미 정렬된 상태로 간주합니다.
결합: 두 부분 배열을 병합하며 정렬합니다.

예제 코드 (C 언어)

#include <stdio.h>
int sorted[100];

void merge(int list[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (list[i] <= list[j]) {
            sorted[k++] = list[i++];
        } else {
            sorted[k++] = list[j++];
        }
    }
    while (i <= mid) sorted[k++] = list[i++];
    while (j <= right) sorted[k++] = list[j++];
    for (int l = left; l <= right; l++) {
        list[l] = sorted[l];
    }
}

void mergesort(int list[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergesort(list, left, mid);
        mergesort(list, mid + 1, right);
        merge(list, left, mid, right);
    }
}

int main() {
    int list[4] = {27, 12, 20, 25};
    mergesort(list, 0, 3);
    for (int i = 0; i < 4; i++) {
        printf("%d ", list[i]);
    }
    return 0;
}