Python 병합정렬 구현

1 개요

Python 병합정렬 구현

def merge(arr, left, middle, right):
	n1 = middle - left + 1
	n2 = right - middle
	L = [0] * (n1)
	R = [0] * (n2)
	for i in range(0 , n1):
		L[i] = arr[left + i]
	for j in range(0 , n2):
		R[j] = arr[middle + 1 + j]
	i = j = 0
	k = left
	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 merge_sort(arr, left, right):
	if left < right:
		middle = int((left+(right-1))/2)
		merge_sort(arr, left, middle)
		merge_sort(arr, middle+1, right)
		merge(arr, left, middle, right)
arr = [3,4,2,1,7,5,8,9,0,6,100,10]
merge_sort(arr, 0, len(arr)-1)
print( arr )
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]

2 같이 보기

• 병합정렬 구현
• 병합정렬