병합 정렬 (Merge Sort)

구현 코드 예시

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

left[i] <= right[j]에서 등호를 빼고 <로만 쓰면 값이 같을 때 오른쪽을 먼저 집는다. 그러면 원래 왼쪽에 있던 원소가 뒤로 밀려 안정성이 깨진다. 안정 정렬이 필요한 상황(예: 이미 이름순으로 정렬된 데이터를 점수순으로 다시 정렬하면서 동점자는 이름순을 유지하고 싶을 때)에서 이 등호 하나가 결과를 바꾼다.

안정 정렬이란

값이 같은 원소들의 원래 순서가 정렬 후에도 유지되는 성질이다. 예를 들어 [("김", 90), ("이", 80), ("박", 90)]을 점수 기준으로 정렬할 때, 안정 정렬은 90점인 김과 박의 순서를 그대로 둔다. 불안정 정렬은 뒤바꿀 수 있다.

주요 정렬의 안정성은 이렇게 갈린다.

파이썬의 sorted()와 list.sort()는 병합 정렬을 개량한 Timsort를 쓰기 때문에 안정 정렬이다. 자바도 객체 배열 정렬에는 Timsort를, 기본형 배열에는 불안정한 듀얼 피벗 퀵 정렬을 쓴다.

자주 하는 실수

• 재귀 종료 조건을 len(arr) == 0으로 쓴다. 원소가 1개일 때 멈추지 않으면 계속 자기 자신을 쪼개며 무한 재귀에 빠진다.
• 병합 마지막에 남은 원소를 안 붙인다. while은 한쪽이 바닥나면 끝나므로, 남은 쪽을 extend로 붙이는 두 줄이 반드시 필요하다.
• 부등호에서 등호를 뺀다. 안정성이 깨진다. 위 설명 참고.
• 재귀 깊이를 넘긴다. 파이썬 기본 재귀 한도는 1000이라 n이 크면 위험하다. 코딩테스트에서는 sys.setrecursionlimit(10**6)을 걸어두는 편이 안전하다.
• 슬라이싱 비용을 무시한다. arr[:mid]는 복사를 만들어 매 단계 O(n)을 추가로 쓴다. 성능이 중요하면 인덱스 범위만 넘기는 방식으로 바꾼다.

면접에서 이렇게 물어본다

• 병합 정렬이 항상 O(n log n)인 이유를 설명해 보라.
• 퀵 정렬이 평균적으로 더 빠른데 병합 정렬을 쓰는 이유는 무엇인가.
• 안정 정렬이 무엇이고 병합 정렬이 안정적인 이유는 무엇인가.
• 병합 정렬의 공간 복잡도가 O(n)인 이유와 이를 줄일 방법이 있는가.
• 연결 리스트를 정렬한다면 병합 정렬과 퀵 정렬 중 무엇이 유리한가.
• 병합 과정을 응용해 배열의 역순 쌍 개수를 세려면 어떻게 하겠는가.