병합 정렬 (Merge Sort)
목차
재귀용법을 활용한 정렬 알고리즘.
- 리스트를 절반으로 자른다
- 재귀적으로 하나가 될 때까지 나눈다
- 나누어진 리스트를 재귀적으로 합병 정렬한다
구현
def merge(left, right):
merged = list()
left_idx, right_idx = 0, 0
while len(left) > left_idx and len(right) > right_idx:
if left[left_idx] > right[right_idx]:
merged.append(right[right_idx])
right_idx += 1
else:
merged.append(left[left_idx])
left_idx += 1
while len(left) > left_idx:
merged.append(left[left_idx])
left_idx += 1
while len(right) > right_idx:
merged.append(right[right_idx])
right_idx += 1
return merged
def split(data):
if len(data) <= 1:
return data
mid = int(len(data) / 2)
left, right = data[:mid], data[mid:]
return merge(split(left), split(right))시간 복잡도
단계는 항상 log n개, 단계별 시간 복잡도는 n: O(n log n)