병합 정렬 (Merge Sort)

병합 정렬이란?

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 대표적인 정렬 알고리즘이다.
배열을 작게 쪼개서 정렬한 뒤, 다시 합치면서 전체를 정렬해나가는 방식이다.

핵심 개념 요약

Divide (분할)

배열을 반으로 나눈다.
더 이상 나눌 수 없을 때까지 계속 쪼갠다 (즉, 길이가 1이 될 때까지).

Conquer (정복)

쪼개진 배열을 병합하며 정렬한다.
두 개의 정렬된 배열을 하나의 정렬된 배열로 합친다

병합 정렬 흐름

예를 들어 배열이 아래와 같다고 해보자:

[21, 10, 12, 20, 25, 13, 15, 22]

그림처럼 병합 정렬은 이 배열을 계속 반으로 쪼개고, 마지막에는 정렬된 조각들을 차례로 병합한다:

가장 아래에선 [21], [10] 같이 한 원소짜리 배열이 만들어짐
그 다음 단계에선 [10, 21], [12, 20]처럼 병합하며 정렬된 두 원소 배열이 생김
마지막엔 전체가 정렬된 하나의 배열로 완성됨

병합(Combine) 과정 자세히 보기

두 정렬된 배열을 병합하는 핵심 로직은 다음과 같다:

두 배열 각각 앞에서부터 비교
더 작은 값을 먼저 새로운 배열(sorted)에 추가
한쪽이 먼저 다 끝나면, 남은 쪽은 그대로 복사

아래 그림은 이 병합 과정을 실제로 시각화한 것이다:

왼쪽: [10, 12, 20, 21]
오른쪽: [13, 15, 22, 25]
결과: [10, 12, 13, 15, 20, 21, 22, 25]

코드

void merge(int p, int q, int r) {
    int i = p, j = q + 1, t = 0;
    
    // 두 포인터를 비교하며 tmp에 복사
    while (i <= q && j <= r) {
        if (A[i] <= A[j]) tmp[t++] = A[i++];
        else tmp[t++] = A[j++];
    }
    
    // 남은 값들 마저 복사
    while (i <= q) tmp[t++] = A[i++];
    while (j <= r) tmp[t++] = A[j++];

    // tmp → A 복사
    i = p; t = 0;
    while (i <= r) {
        A[i++] = tmp[t++];
    }
}

void merge_sort(int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(p, q);        // 왼쪽 정렬
        merge_sort(q + 1, r);    // 오른쪽 정렬
        merge(p, q, r);          // 병합
    }
}

시간 복잡도

케이스복잡도

최선	O(N log N)
평균	O(N log N)
최악	O(N log N)

항상 안정적인 성능을 보장함
데이터가 이미 정렬되어 있어도 시간 복잡도는 변하지 않음

안정 정렬

안정 정렬이란? 값이 같은 원소들의 원래 순서가 유지되는 정렬
병합 정렬에서는 같은 값이 있을 경우, 먼저 등장한 값을 먼저 복사하기 때문에 안정성이 유지됨
예: (A, 3)와 (B, 3)이 있다면 정렬 후에도 A가 B보다 앞에 옴

참고: 병합 정렬이 활용된 예제

백준 24060번 : 병합 정렬을 수행하면서 "배열에 저장되는 순간"을 추적하는 문제

저작자표시 (새창열림)