[Algo] 병합정렬

병합정렬

병합 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택하는 방법이다.
즉, 정확히 반으로 나누고 나중에 정렬한다.

💯 시간 복잡도는 무조건 NlogN

def merge_sort(lst):
    if len(lst) == 1:
        return lst

    # 절반으로 나누기
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])

    # 합치기
    ret = []
    while left and right:
        if left[0] < right[0]:
            ret.append(left.pop(0))
        else:
            ret.append(right.pop(0))

    # 어차피 비어있는 리스트라면 더해지는게 없으니 조건문x
    ret.extend(left)
    ret.extend(right)

    return ret

arr = [7, 6, 5, 8, 3, 5, 9, 1]
sorted_lst = merge_sort(arr)
print(sorted_lst)

⭐ index 버전

def merge_sort(s,e):
	if s == e:
			return
	mid = (s + e) // 2
	merge_sort(s,mid)
	merge_sort(mid+1,e)

	i, j, k = s, mid + 1, s 
	while i <= mid and j <= e:
		if arr[i] < arr[j]:
			tmp[k] = arr[i] ; i, k = i+1, k+1				
		else : 
			tmp[k] = arr[j] ; j, k = j+1, k+1
		
	while i <= mid
		tmp[k] = arr[i] ; i, k = i+1, k+1	
	while j <= e
		tmp[k] = arr[j] ; j, k = j+1, k+1	
		
	for i in range(s,e+1)
		arr[i] = tmp[i]
		
		
arr = [69,30,10,2,16,8,32,21]
tmp = [0] * len(arr)
merge_sort(0,len(arr) - 1)
pirnt(arr)