합병 정렬

정의
합병 정렬(merge sort)은 비교 기반 정렬 알고리즘의 하나로, 데이터를 여러 부분으로 재귀적으로 분할한 뒤, 각각을 정렬하고 다시 합병(merge)하는 과정을 통해 전체 데이터를 정렬한다.

알고리즘 구조

1. 분할(Divide)

   • 입력 배열을 반으로 나누어 두 개의 하위 배열을 만든다.
   • 하위 배열이 더 이상 분할할 수 없을 때까지(길이가 1이 될 때까지) 재귀적으로 분할한다.

2. 정복(Conquer)

   • 길이가 1인 하위 배열은 이미 정렬된 것으로 간주한다.

3. 합병(Merge)

   • 두 개의 정렬된 하위 배열을 순차적으로 비교하면서 새로운 배열에 차례대로 삽입한다.
   • 이 과정은 선형 시간 O(n)으로 수행된다.

시간 복잡도

공간 복잡도

• 추가적인 임시 배열을 사용하므로 일반적인 구현에서는 O(n)의 보조 공간이 필요하다. 인플레이스(in‑place) 구현도 존재하지만 구현 난이도가 높다.

특징

• 안정성: 동일한 키 값을 가진 원소들의 상대 순서가 유지된다(안정 정렬).
• 분할 정복: 재귀적 구조를 이용해 문제를 작은 부분 문제로 나눠 해결한다.
• 병렬 처리에 유리: 각 하위 배열을 독립적으로 정렬할 수 있어 멀티코어 환경에서 효율적으로 구현될 수 있다.

역사·출처
합병 정렬은 1945년 존 폰 노이만(John von Neumann)이 최초로 제안한 것으로 알려져 있다. 이후 1960년대에 컴퓨터 과학 교과서와 실무에서 널리 채택되면서 표준적인 정렬 알고리즘 중 하나가 되었다.

적용 사례

• 외부 정렬(External sorting)에서 큰 데이터 집합을 디스크와 메모리 사이에 나누어 정렬할 때 사용된다.
• 병렬 컴퓨팅 환경에서 각 프로세스가 부분 데이터를 정렬한 뒤 최종 합병 단계에서 전체 정렬을 완성하는 경우에 활용된다.
• 안정 정렬이 요구되는 상황(예: 데이터베이스 정렬, 다중 키 정렬)에서 선택적으로 사용된다.

구현 예시 (Python)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged

참고

• 합병 정렬은 “merge sort”라는 영어 명칭으로도 동일하게 알려져 있다.
• 자세한 수학적 증명 및 변형(예: 튜플 합병, 인플레이스 합병 등)은 전산학 교과서 및 알고리즘 전문서적을 참조한다.