Python의 병합 정렬(merge sort)
이 레슨에서는 재귀 함수를 이용해 분할 정복 전략으로 병합 정렬을 구현합니다.
소개
어떤 문제를 해결하나요
단순한 정렬은 리스트가 커지면 눈에 띄게 느려집니다. 데이터가 두 배가 되면 할 일은 네 배가 됩니다. 병합 정렬은 문제를 풀기 쉬운 작은 문제들로 나눕니다. 덕분에 할 일이 데이터보다 조금만 더 빨리 늘어납니다.
일상 속 비유
병합 정렬은 높이 쌓인 시험지를 친구들과 함께 정렬하는 것과 같습니다. 시험지 더미를 반으로 나눠 친구들에게 하나씩 넘깁니다. 친구들도 받은 더미를 다시 반으로 나누고, 모두가 한 장씩 들 때까지 계속합니다. 그런 다음 두 사람씩 짝을 지어 정렬된 더미를 합칩니다. 두 더미의 맨 위 시험지 중 더 작은 쪽을 계속 가져오면 됩니다. 정렬된 더미 하나가 남으면 끝입니다.
if len(values) <= 1:📄 한 장짜리는 이미 정렬된 상태merge_sort(values[:middle])✂️ 더미를 반으로 나누고 절반씩 정렬left[left_index] <= right[right_index]🤝 합치기: 맨 위 시험지 중 더 작은 쪽 가져오기result + left[left_index:] + right[right_index:]📚 다른 더미에 남은 시험지를 그대로 붙이기병합 정렬은 리스트를 반으로 나누고, 각 절반을 재귀로 정렬한 다음, 정렬된 두 절반을 하나로 합칩니다. O(n log n) 시간이 걸립니다.
핵심 포인트
if len(values) <= 1: return values는 재귀를 멈추는 기저 사례(base case)입니다.merge_sort(values[:middle])와merge_sort(values[middle:])가 두 절반을 각각 정렬합니다.while반복문은left와right의 맨 앞 값 중 더 작은 쪽을 가져옵니다. 한쪽 리스트가 바닥날 때까지 계속합니다.left[left_index:]와right[right_index:]는 남은 값을 뒤에 붙입니다. 남은 값은 이미 정렬되어 있습니다.<=를 쓰면 두 값이 같을 때 왼쪽 것을 먼저 가져오므로, 같은 값끼리는 원래 순서가 유지됩니다.
언제 사용하나요?
- 큰 데이터를 늘 일정하게 빠른 속도로 정렬할 때. 유난히 느려지는 최악의 경우가 없습니다.
- 연결 리스트나, 메모리에 다 올릴 수 없을 만큼 큰 데이터의 정렬(외부 정렬).
- 많은 알고리즘이 쓰는 분할 정복(divide and conquer) 패턴을 배울 때.
필요 없는 경우
- 일반적인 Python 코드:
sorted()는 이미 Timsort를 씁니다. 병합 정렬과 삽입 정렬을 섞어 다듬은 알고리즘입니다. - 메모리가 아주 빠듯한 경우: 병합 정렬은 합친 리스트를 담을 공간이 따로 필요합니다.
Python의 병합 정렬(merge sort) 시각화
O(n log n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
실행 결과
[3, 9, 10, 27, 38, 43, 82]
코드 설명
재귀 함수는 각 조각에 요소가 하나만 남을 때까지 리스트를 나눕니다. 요소가 하나뿐인 리스트는 언제나 정렬된 상태이기 때문입니다. 그다음 while 반복문이 두 부분 리스트의 맨 앞 요소 중 더 작은 쪽을 계속 골라 합칩니다. 이 알고리즘은 항상 O(n log n)에 실행되며 O(n)의 추가 메모리가 필요합니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
남은 값을 잊어버리기
한쪽 절반이 바닥났을 때, 다른 쪽 절반에 남아 있던 값들이 버려집니다.
return result
return result + left[left_index:] + right[right_index:]
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지