병합 정렬의 분할과 합치기

이미 정렬된 목록 둘을 합치는 일은 전체를 다시 정렬하는 것보다 단순합니다. 목표는 분할·재귀·병합 세 단계의 역할과 안정성을 설명하는 것입니다. 재귀의 기저 사례와 리스트 슬라이스를 복습하세요.

개념과 약속

길이가 0 또는 1이면 이미 정렬되어 있습니다. 그보다 길면 반으로 나누어 각각 정렬합니다. 병합은 정렬된 두 목록의 맨 앞 원소 중 작은 것을 결과에 넣고 해당 목록의 위치만 한 칸 움직이는 작업입니다. 한쪽이 끝나면 다른 쪽의 남은 원소를 그대로 붙입니다.

같은 값이면 왼쪽을 먼저 택하는 <=로 동률의 원래 순서를 보존합니다. 이 구현은 슬라이스와 새 목록을 사용하는 읽기 쉬운 버전입니다. 제자리 정렬이라고 설명하지 않습니다.

손으로 상태 추적하기

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def merge_sort(values):
    if len(values) <= 1:
        return list(values)
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    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
    return result + left[i:] + right[j:]


print(merge_sort([4, 2, 3, 1]))
print(merge_sort([3, 1, 3]))
print(merge_sort([]))

실행 결과:

[1, 2, 3, 4]
[1, 3, 3]
[]

왜 맞고 언제 끝나는가

두 목록의 맨 앞이 각 목록에서 가장 작으므로 그중 작은 것을 고르면 남은 전체에서도 가장 작은 값입니다. 따라서 결과는 매 단계 정렬된 앞부분입니다. 정렬된 작은 결과를 병합하므로 큰 결과도 정렬됩니다. 분할된 길이는 원래보다 작고 병합 위치는 증가해 종료합니다.

비용과 적용 범위

한 병합은 원소를 한 번씩 처리해 O(n), 분할 깊이는 O(log n)이므로 최악 시간 O(n log n)입니다. 이 구현의 동시에 살아 있는 목록과 결과의 추가 공간은 O(n), 호출 깊이는 O(log n)입니다. 전체 실행 동안 생성·해제되는 누적 복사량과 최고 동시 공간은 다릅니다.

스스로 풀어 보기

1. [1,3,5]와 [2,4,6]을 병합할 때 선택한 목록의 순서를 쓰세요.
2. 같을 때 오른쪽을 먼저 고르면 숫자 결과와 안정성은 각각 어떻게 되나요?

힌트

1. 매번 두 맨 앞을 비교합니다.
2. 왼쪽의 동률 항목이 원래 더 앞에 있었습니다.

해설

1. 왼쪽·오른쪽·왼쪽·오른쪽·왼쪽·오른쪽입니다.
2. 숫자는 여전히 오름차순이지만 동률 항목의 상대 순서가 뒤집힐 수 있습니다. 정렬 정확성과 안정성은 다른 성질입니다.

흔한 오해

병합은 아무 두 목록에나 적용해 정렬 결과를 만드는 마술이 아닙니다. 각 입력이 이미 정렬되었다는 전제가 꼭 필요합니다.

복습과 다음 연결

퀵 정렬은 먼저 분할 기준을 정합니다. 메모리보다 큰 자료의 병합은 외부 정렬에서 다룹니다.