merge sort는 어떻게 동작하나요?

Question

Accepted Answer

**Merge sort**는 보장된 **O(n log n)** 시간에 동작하는 **분할 정복** 방식의 **안정** 정렬입니다. 배열을 절반으로 나누고, 각 절반을 재귀적으로 정렬한 뒤, 정렬된 두 절반을 병합합니다.

## 개념

원소 하나는 이미 정렬된 상태입니다(base case). 정렬된 두 리스트를 병합하는 것은 선형이며, log n개의 병합 단계가 있습니다.

## 예시

```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(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:              # <= 로 안정성 유지
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:]); result.extend(b[j:])
    return result

merge_sort([5, 2, 4, 1, 3])           # -> [1, 2, 3, 4, 5]
```

## 복잡도

- **시간:** *모든* 경우(최선, 평균, 최악)에 O(n log n).
- **공간:** 병합 버퍼를 위한 O(n)(제자리 정렬 아님).

## 언제 사용하나 / 함정

**안정성**이나 보장된 O(n log n)이 필요할 때, 그리고 **연결 리스트**와 거대한 파일의 **외부 정렬**에 이상적입니다. 추가 O(n) 메모리가 주요 단점입니다.

## 왜 중요한가

Merge sort는 quicksort의 O(n²) 최악 경우와 달리 입력에 관계없이 O(n log n)을 보장합니다.

안정성은 같은 키의 상대적 순서를 보존하는데, 이는 다중 키 정렬에서 중요합니다.

병합 단계는 재사용 가능한 기본 연산이며, 분할 정복 구조는 어디서든 재사용할 템플릿입니다.

개념

예시

question.related

복잡도

언제 사용하나 / 함정

왜 중요한가