[Python] 병합 정렬

ungnam·2025년 3월 4일

1. 병합 정렬이란?

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한 정렬 방법 중 하나다. 리스트를 반으로 나누고, 각각을 정렬한 후 병합하는 과정을 반복하여 정렬을 수행한다. 병합 정렬의 시간 복잡도는 최악의 경우에도 O(n log n)을 유지하며, 안정 정렬(Stable Sort) 이라는 장점을 갖고 있다.

2. 병합 정렬의 원리

병합 정렬은 다음과 같은 원리로 동작한다:

분할(Divide) → 리스트를 반으로 나눈다.
정복(Conquer) → 나눈 리스트를 재귀적으로 정렬한다.
병합(Merge) → 정렬된 두 리스트를 하나로 합친다.

이 과정을 반복하면 전체 리스트가 정렬된다.

3. 병합 정렬 구현

3.1 두 리스트를 병합하는 함수

from typing import Sequence, MutableSequence
import heapq

def merged_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None:
    """
    두 개의 정렬된 리스트 a와 b를 병합하여 정렬된 리스트 c에 저장한다.
    - a, b: 정렬된 입력 리스트
    - c: 병합된 결과를 저장할 리스트
    """
    pa, pb, pc = 0, 0, 0
    na, nb, nc = len(a), len(b), len(c)

    # a와 b를 비교하여 더 작은 값을 c에 저장
    while pa < na and pb < nb:
        if a[pa] <= b[pb]:
            c[pc] = a[pa]
            pa += 1
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1

    # a에 남아 있는 원소를 c에 복사
    while pa < na:
        c[pc] = a[pa]
        pa += 1
        pc += 1

    # b에 남아 있는 원소를 c에 복사
    while pb < nb:
        c[pc] = b[pb]
        pb += 1
        pc += 1

✔ a와 b는 각각 정렬된 상태이며, 두 리스트를 비교하면서 c에 차례로 저장한다.
✔ sorted(a + b)를 이용하면 리스트를 합친 후 정렬하는 간단한 방법이지만, 추가적인 메모리가 필요하다.
✔ heapq.merge(a, b)를 사용하면 힙을 이용해 효율적으로 정렬할 수 있다.

3.2 재귀적인 병합 정렬 구현

from typing import MutableSequence

def merge_sort(a: MutableSequence) -> None:
    def _merge_sort(a: MutableSequence, left: int, right: int, buff: MutableSequence) -> None:
        if left < right:
            center = (left + right) // 2
            _merge_sort(a, left, center, buff)  # 왼쪽 부분 정렬
            _merge_sort(a, center + 1, right, buff)  # 오른쪽 부분 정렬

            p, j = 0, 0  # 보조 리스트 인덱스
            i, k = left, left  # 원래 리스트 인덱스

            # 왼쪽 리스트를 보조 리스트(buff)에 복사
            while i <= center:
                buff[p] = a[i]
                p += 1
                i += 1

            # 오른쪽 리스트와 비교하여 병합 수행
            while i <= right and j < p:
                if buff[j] <= a[i]:
                    a[k] = buff[j]
                    j += 1
                else:
                    a[k] = a[i]
                    i += 1
                k += 1
            
            # 왼쪽 리스트에 남아 있는 값 복사
            while j < p:
                a[k] = buff[j]
                k += 1
                j += 1

    n = len(a)
    buff = [None] * n  # 보조 리스트 생성
    _merge_sort(a, 0, n - 1, buff)
    del buff  # 사용이 끝난 보조 리스트 삭제

✔ 리스트 a의 앞부분을 리스트 buff로 복사한다.
✔ 배열 a의 뒷부분과 배열 buff를 배열 a에 병합한다.
✔ 배열 buff의 나머지 원소를 배열 a에 복사한다.
✔ 이 때 배열 a에 원소가 남는 경우는 이미 배열 a에 반영이 되었기 때문에 따로 케이스를 고려하지 않는다.