합병 정렬(Merge Sort) 의 개념
합병 정렬도 퀵 정렬처럼 분할정복 방법을 통해서 데이터를 정렬합니다. 주어진 배열을 동일한 크기의 두 개의 부분배열로 분할하고, 각각의 부분배열을 순환적으로 합병 정렬을 한 후, 정렬된 두 개의 부분배열을 합병하여 하나의 정렬된 배열을 만드는 방식입니다.
합병 정렬의 Python 구현
Python 으로 퀵 정렬을 아래와 같이 구현할 수 있습니다.
def merge_sort(arr: list) -> list:
# 배열의 길이가 1 이하면 이미 정렬된 것으로 간주하고 반환
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: list, right: list) -> list:
result = [] # 두 배열을 합쳐 정렬된 결과를 저장할 배열
i = j = 0 # 각각 left, right 배열의 인덱스를 추적
# left와 right 배열을 탐색하며 더 작은 요소를 result에 추가
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
위의 python 코드는 아래와 같이 동작합니다.
아래의 배열은 먼저 두 개의 부분배열로 나뉩니다.
left | right
[1, 3, 2, 5, 4]또, 이 배열들에 대해서 재귀적으로 merge_sort 를 호출하므로 아래와 같이 또 부분배열로 나뉩니다. (왼쪽 부분에 대해서 merge_sort 를 재귀적으로 호출하고, 오른쪽 부분에 대해서 merege_sort 를 호출합니다.)
# 부분배열 나누기
left | right
[1, 3, 2, 5, 4]
# merge_sort 재귀 호출 ...
-> [1, 3, 2], [5, 4]
-> [[1], [3, 2]], [[5], [4]] # 왼쪽 분할 후 오른쪽 분할
-> [[1], [[3],[2]], [[5], [4]] # 왼쪽 분할 후 오른쪽 분할
분할 과정이 완료되면, 정렬된 부분들에 대해서 _merge 를 통해서 정렬된 부분배열들을 만듭니다.
# 분할된 배열
[[1], [[3],[2]], [[5], [4]]
# _merge 를 호출해 정렬된 배열 만들기
[[1], [2, 3]] [[5], [4]]
-> [1], [2, 3], [4, 5]
-> [1, 2, 3], [4, 5]
-> [1, 2, 3, 4, 5] 합병 정렬의 성능 분석과 특징
- 합병 함수
_merge에서 크기가m인 배열과 크기가n인 배열을 합병하면, 결과 배열에는 원소가(m + n)개의 원소가 저장됩니다.- 그 과정에서, 최악의 경우
n + m - 1회의 비교가 필요합니다.
- 그 과정에서, 최악의 경우
- 합병 정렬의 경우, 두 부분의 부분배열의 크기가 동일하기 때문에 최악의 비교 횟수는
n-1이 됩니다.- 결국 합병을 하는 데 걸리는 시간은
O(n)이 됩니다.
- 결국 합병을 하는 데 걸리는 시간은
- 분할된 단계에서 생성된 부분배열에 대해서 합병이 이루어지므로, 전체 시간 복잡도는
O(nlogn)이 됩니다.