코드
# 병합 정렬
def merge_sort(nums):
N = len(nums)
if N <= 1: #길이가 1이하이면 더이상 분할이 불가능
return nums
mid = N//2 #길이가 2이상이면 분할
left_nums = nums[:mid]
right_nums = nums[mid:]
left = merge_sort(left_nums) #분할한 왼쪽 리스트에 대해서 다시 병합정렬
right = merge_sort(right_nums) #분할한 오른쪽 리스트에 대해 다시 병합정렬
return merge(left, right) #분할한 왼쪽, 오른쪽 리스트를 병합
# 병합
def merge(left, right):
left_idx, right_idx = 0, 0
L, R = len(left), len(right)
merged_nums = []
while left_idx < L and right_idx < R:
if left[left_idx] <= right[right_idx]:
merged_nums.append(left[left_idx])
left_idx += 1
else:
merged_nums.append(right[right_idx])
right_idx += 1
for i in range(left_idx, L):
merged_nums.append(left[i])
for j in range(right_idx, R):
merged_nums.append(right[j])
return merged_nums
print(merge_sort([19, 10, 3, 5, 13, 4, 12, 17, 8, 16]))
stack overflow
가 발생할 때까지 호출이 계속 될 것이므로 종료조건을 잘 설정해주는 것이 중요O(N logN)
으로 좋은 성능을 가진 정렬 알고리즘이지만, 최악의 경우 O(N^2)
의 시간복잡도를 가짐pivot
으로 선택되었는지에 따라 갈리기 때문에 pivot
을 선택하는 방법 역시 퀵 정렬의 중요한 요소