병합정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 O(nlogn)이다
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬방법이다. 이때 병합 정렬은 아래와 같은 분할 정복 메커니즘을 따르게 된다
병합정렬; 오름차순
*이 때 그림에서 표현은 생략되었으나 부분 리스트의 크기가 1이 될 때까지 분할 후 정렬 후 합병과정을 거치게 된다
def merge_sort(unsorted_list):
# 크기가 1이하면 반환
if len(unsorted_list) <= 1:
return unsorted_list
# 리스트를 2분할
mid = len(unsorted_list)//2
left = unsorted_list[:mid]
right = unsorted_list[mid:]
# 2분할한 리스트를 각각 merge sort진행
left_ = merge_sort(left)
right_ = merge_sort(right)
return merge(left_, right_)
def merge(left, right):
i, j = 0,0
sorted_list = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_list.append(left[i])
i += 1
else:
sorted_list.append(right[j])
j += 1
while i < len(left):
sorted_list.append(left[i])
i += 1
while j < len(right):
sorted_list.append(right[j])
j += 1
return sorted_list
print(merge_sort(unsorted_list))