[알고리즘 심층분석 #5] 병합 정렬(Merge Sort) 분할 정복, O(N log N) 보장, 메모리 O(N) 완벽 정리

퀵 정렬과 함께 대표적인 고급 분할 정복 알고리즘으로 꼽히는 병합 정렬(Merge Sort)입니다.

"어떤 상황에서도 항상 O(N log N)의 안정적인 성능을 내는 비결은 무엇일까?"

"왜 병합 정렬은 제자리 정렬이 불가능하고 O(N) 크기의 별도 메모리 공간이 필요할까?"

병합 정렬의 핵심 메커니즘부터 단계별 동작 과정, 파이썬 코드 구현, 복잡도 유도, 그리고 시험에 꼭 나오는 안정 정렬(Stable Sort)의 특성까지 심층 분석해 드립니다!

1. 병합 정렬(Merge Sort)이란?

병합 정렬은 존 폰 노이만(John von Neumann)이 제안한 분할 정복(Divide and Conquer) 기법 기반의 정렬 알고리즘입니다.

• 핵심 전략 (분할 정복 3단계):
  1. 분할 (Divide): 정렬할 배열을 동일한 크기의 두 부분 배열로 반씩 나눕니다.
  2. 정복 (Conquer): 나뉜 부분 배열의 크기가 1이 될 때까지 재귀적으로 병합 정렬을 적용합니다. (크기가 1인 배열은 이미 정렬된 것으로 간주)
  3. 결합 (Combine / Merge): 정렬된 두 개 이상의 부분 배열을 하나의 정렬된 배열로 합치면서(Merge) 최종 정렬을 완성합니다.

배열을 최소 단위로 분할한 뒤 정렬하면서 합치는 병합 정렬 메커니즘. 출처: vectorwin / Getty Images

2. 단계별 동작 예시 (Step-by-Step)

배열 [38, 27, 43, 3, 9, 82, 10]을 오름차순으로 정렬하는 과정입니다.

• 1단계: 분할 (Divide)
  • [38, 27, 43, 3, 9, 82, 10]
  • [38, 27, 43, 3] / [9, 82, 10]
  • [38, 27] / [43, 3] / [9, 82] / [10]
  • [38] [27] [43] [3] [9] [82] [10] (크기 1로 완전히 분할 완료)
• 2단계: 병합 및 정복 (Combine / Merge)
  • 두 개씩 크기를 비교하며 합칩니다.
  • [27, 38] / [3, 43] / [9, 82] / [10]
  • [3, 27, 38, 43] / [9, 10, 82]
  • 최종 병합: [3, 9, 10, 27, 38, 43, 82] 완료!

3. 코드 구현 (Python)

Python

 

def merge_sort(arr):
    # Base Case: 원소가 1개 이하면 이미 정렬된 상태
    if len(arr) <= 1:
        return arr
    
    # 1. 분할 (Divide)
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])   # 왼쪽 재귀 분할
    right_half = merge_sort(arr[mid:])  # 오른쪽 재귀 분할
    
    # 2. 결합 (Combine)
    return merge(left_half, right_half)

def merge(left, right):
    sorted_arr = []
    i = j = 0
    
    # 두 부분 배열의 원소를 비교하며 작은 값을 결과 배열에 추가
    while i < len(left) and j < len(right):
        # <= 비교 연산을 사용하여 안정 정렬(Stable Sort) 유지
        if left[i] <= right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
            
    # 남은 원소들을 뒤에 붙여줌
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    
    return sorted_arr

4. 복잡도 및 특성 분석 (★시험 단골 출제)

🔹 시간 복잡도: 항상 O(N log N) 보장

• 분할 단계 (log N): 배열을 계속 반으로 나눌 때 트리 구조의 높이는 항상 log N이 됩니다. (데이터 입력 상태와 전혀 무관)
• 병합 단계 (N): 각 층(Level)마다 모든 원소 N개를 일일이 비교하며 합치므로 각 층당 O(N)의 시간이 소요됩니다.
• 결합: 따라서 최선, 평균, 최악 모두 예외 없이 O(N log N)이라는 균일한 성능을 보장합니다.

🔹 공간 복잡도: O(N) (★시험 서술형 단골)

• 이유: 병합 과정에서 정렬된 두 부분 배열의 값을 순서대로 담아둘 임시 임시 배열(Extra Space)이 추가로 필요합니다.
• 따라서 입력 배열의 크기 N만큼의 추가 메모리 공간이 요구되므로 제자리 정렬(In-Place Sort)이 아닙니다.

🔹 안정성 (Stability)

• 병합할 때 두 값이 같으면(left[i] <= right[j]) 항상 왼쪽 배열의 원소를 먼저 선택하도록 구현할 수 있습니다.
• 이에 따라 원래 순서가 뒤바뀌지 않는 대표적인 안정 정렬(Stable Sort)입니다.

5. 퀵 정렬 vs 병합 정렬 한눈에 비교

비교 항목	퀵 정렬 (Quick Sort)	병합 정렬 (Merge Sort)
시간 복잡도 (최선/평균)	O(N log N)	O(N log N)
시간 복잡도 (최악)	O(N^2) (피봇 편향 시)	O(N log N) (항상 보장)
공간 복잡도	O(log N) (제자리 정렬)	O(N) (추가 메모리 필요)
안정성 (Stability)	불안정 정렬 (Unstable)	안정 정렬 (Stable)
적합한 데이터 구조	배열(Array) - 캐시 효율 높음	연결 리스트(Linked List) - 메모리 재할당 부담 없음

6. 한눈에 끝내는 핵심 요약표 (★시험 필수)

구분	주요 내용 및 특징
기본 매커니즘	반으로 쪼갠 뒤(Divide) 정렬하며 합침(Merge)
시간 복잡도	최악, 평균, 최선 모두 O(N log N)
공간 복잡도	O(N) (임시 배열 필요)
안정성 여부	안정 정렬 (Stable Sort)
장단점	최악에도 O(N log N)을 보장하나, 추가 메모리 O(N) 소요가 단점