병합 정렬(Merge Sort)이란?
병합 정렬은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 배열을 반으로 계속 나누어 더 이상 나눌 수 없을 때까지 분할한 뒤, 작은 단위부터 차례대로 정렬하면서 병합해 나가는 방식으로 동작합니다.
이 글에서는 아래 문제를 Python으로 해결하는 과정을 단계별로 살펴보겠습니다.
문제 정의 - 주어진 배열을 병합 정렬 알고리즘을 활용해 오름차순으로 정렬해야 합니다.
병합 정렬의 동작 원리
- 분할(Divide) : 배열을 중간 지점을 기준으로 두 개의 하위 배열로 나눕니다.
- 정복(Conquer) : 각 하위 배열을 재귀적으로 병합 정렬합니다.
- 병합(Merge) : 정렬된 두 하위 배열을 하나의 정렬된 배열로 합칩니다.
Python 구현 예제
# 병합(merge) 함수
def merge(arr, l, m, r):
n1 = m - l + 1 # 왼쪽 하위 배열의 크기
n2 = r - m # 오른쪽 하위 배열의 크기
# 임시 배열 생성
L = [0] * n1
R = [0] * n2
# 데이터 복사
for i in range(n1):
L[i] = arr[l + i]
for j in range(n2):
R[j] = arr[m + 1 + j]
i = 0 # 왼쪽 배열의 인덱스
j = 0 # 오른쪽 배열의 인덱스
k = l # 병합 결과가 저장될 위치
# 두 하위 배열을 비교하며 정렬된 순서로 병합
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# 왼쪽 배열에 남은 요소 복사
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# 오른쪽 배열에 남은 요소 복사
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# 병합 정렬 함수
def mergeSort(arr, l, r):
if l < r:
# 중간 지점 계산
m = (l + r) // 2
# 각 절반을 재귀적으로 정렬
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
# 정렬된 두 절반을 병합
merge(arr, l, m, r)
# 메인 실행부
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
mergeSort(arr, 0, n - 1)
print('정렬된 배열:')
for i in range(n):
print(arr[i], end=' ')
실행 결과
정렬된 배열: 2 3 4 5 5 6 7 8
코드 설명
모든 변수는 지역 범위(local scope) 내에서 선언되며, 재귀 호출이 일어날 때마다 독립적인 값이 유지됩니다. merge() 함수는 두 개의 정렬된 하위 배열을 앞에서부터 비교하여 작은 값부터 원래 배열에 채워 넣고, 한쪽 배열의 요소가 모두 소진되면 나머지 요소들을 그대로 복사합니다.
mergeSort() 함수는 배열의 시작 인덱스 l과 끝 인덱스 r을 받아, l < r인 경우에만 중간 지점을 기준으로 배열을 분할하고 재귀 호출을 수행합니다. 요소가 하나뿐인 상태(l == r)에 도달하면 더 이상 분할하지 않으며, 이후 호출 스택을 거슬러 올라가며 병합이 진행됩니다.
시간 및 공간 복잡도
- 시간 복잡도 : 최선, 평균, 최악의 모든 경우에 O(n log n)으로 일정합니다.
- 공간 복잡도 : O(n) - 병합 과정에서 임시 배열이 필요하기 때문입니다.
- 안정성 : 같은 값을 가진 요소들의 상대적 순서가 유지되는 안정 정렬(stable sort)입니다.
결론
이 글에서는 분할 정복 기법을 기반으로 하는 병합 정렬의 원리를 이해하고, 이를 Python으로 구현하는 방법을 배웠습니다. 병합 정렬은 입력 데이터의 초기 상태와 무관하게 항상 O(n log n)의 성능을 보장하기 때문에 대용량 데이터 처리나 연결 리스트 정렬 등에 특히 유용하게 활용됩니다.