병합 정렬(Merge Sort) 알고리즘

개요

병합 정렬(Merge Sort)은 데이터를 반으로 나누고 각각을 정렬한 뒤 다시 병합하는 분할 정복(Divide and Conquer) 전략을 사용하는 효율적인 정렬 알고리즘이다. 안정 정렬이며, 항상 **O(n log n)**의 시간 복잡도를 유지해 정렬 알고리즘 중에서도 높은 성능과 예측 가능성을 보인다. 내부 정렬과 외부 정렬(External Sort) 모두에 활용되며, 대용량 데이터 정렬에도 적합하다.

---

1. 개념 및 정의

병합 정렬은 다음 과정을 반복하여 배열을 정렬한다:

• 배열을 반으로 나눈다 (재귀적으로)
• 각각을 병합 정렬로 정렬한다
• 정렬된 두 부분 배열을 하나로 병합한다

병합 시에는 두 정렬된 배열을 비교하여 하나의 정렬된 배열로 합친다.

---

2. 동작 원리

단계	설명
1	배열을 재귀적으로 반씩 나눔
2	분할된 배열이 길이 1이면 정렬된 상태로 간주
3	두 배열을 정렬하며 병합(merge)
4	병합 결과를 상위 재귀로 전달하며 정렬 완료

분할-정복 패턴의 대표적인 예시로, 재귀 호출 구조가 핵심이다.

---

3. 파이썬 구현 예시

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):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 사용 예시
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

---

4. 시간 및 공간 복잡도

항목	복잡도
최선	O(n log n)
평균	O(n log n)
최악	O(n log n)
공간 복잡도	O(n) (병합 시 배열 복사 필요)

퀵 정렬과는 달리 항상 일정한 성능을 유지하는 장점이 있다.

---

5. 특징 및 장단점

항목	설명
안정 정렬 여부	O (동일 값 순서 유지)
메모리 사용	높음 (배열 병합에 추가 공간 필요)
재귀 기반	O (스택 깊이 = log n)
성능 예측성	항상 일정 (최악도 O(n log n))
외부 정렬 적합	대용량 디스크 기반 정렬 가능

안정성과 성능 예측 면에서 매우 우수하지만 메모리 사용은 많다.

---

6. 시각적 예시 (예: [38, 27, 43, 3, 9, 82, 10])

• 분할: [38, 27, 43, 3] / [9, 82, 10] → 계속 나눔 → [3], [27], [38], ...
• 병합: [27, 38], [3, 43], [9, 10, 82]
• 최종 병합: [3, 27, 38, 43, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

---

7. 다른 정렬 알고리즘과 비교

알고리즘	시간 복잡도	공간 복잡도	안정성	특징
병합 정렬	O(n log n)	O(n)	O	항상 일정한 성능
퀵 정렬	O(n log n)	O(log n)	X	평균 빠름, 최악 O(n²)
삽입 정렬	O(n²)	O(1)	O	정렬된 데이터에 효과적
선택 정렬	O(n²)	O(1)	X	단순, 교환 적음
버블 정렬	O(n²)	O(1)	O	가장 느리지만 단순

---

8. 활용 사례

분야	활용 예시
대용량 파일 정렬	외부 병합 정렬 방식 사용 (파일 기반 병합)
데이터베이스	쿼리 결과 정렬에 안정성 중요할 때
실시간 통계	안정성과 정확성 필요한 환경
알고리즘 대회	빠르고 예측 가능한 정렬이 필요한 경우

특히 안정 정렬이 필요하거나 일관된 성능이 중요한 경우에 유리하다.

---

9. 결론

병합 정렬은 분할과 병합이라는 정렬 로직을 바탕으로 높은 안정성과 일관된 성능을 제공하는 정렬 알고리즘이다. 구현은 상대적으로 복잡하지만, 이해하면 다양한 문제에 안정적인 정렬 성능을 제공할 수 있다. 외부 정렬, 안정 정렬이 필요한 실전 문제나 대용량 데이터 처리에서 필수적으로 알아야 할 알고리즘이다.