병합정렬_MergeSort

병합정렬(Merge Sort)

• 하나의 리스트를 두개의 균일한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.

동작과정

1. Divide - 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다
2. Conquer - 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(left < right) 순환호출을 이용해 다시 분할 정복 방법을 적용한다.
3. Combine - 정렬된 부분 배열들을 하나의 배열에 병합한다.

def merge_sort(arr):
	def sort(low, high):
		if high - low < 2:
			return
		mid= (low + high) // 2
		sort(low, mid)
		sort(mid, high)
		merge(low, mid, high)

	def merge(low, mid, high):
		temp = []
		l,h = low, mid

		while l <mid and h<high:
			if arr[l] < arr[h]:
				temp.append(arr[l])
				l += 1
			else:
				temp.append(arr[h])
				h += 1
		while l < mid:
			temp.append(arr[l])
			l += 1
		while h < high:
			temp.append(arr[h])
			h += 1

		for i in range(low,high):
			arr[i] = temp[i - low]