2023.01.30

병합 정렬.

def merge_sort(a):
    n = len(a)
    if n <= 1:
        return a
    
    mid = n//2
    
    g1 = merge_sort(a[:mid])
    print(g1)
    g2 = merge_sort(a[mid:])
    result = []
    while g1 and g2:
        if g1[0] < g2[0]:
            result.append(g1.pop(0))
        else:
            result.append(g2.pop(0))       
    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))
    return result


d = [6,8,3,9,10,1,2,4,7,5]
print(merge_sort(d))

회고

한번에 이해가 되지 않아서 직접 팬으로 케이스 하나하나 따라가 보면서 이해했다.

• return result를 하는 부분에 재귀함수로 호출된 함수가 종료된다는 점을 놓침.

흐름

g1 = merge_sort(a[6,8,3,9,10])
	g1 = merge_sort(a[6,8])
		g1 = merge_sort([6])
		g2 = merget_sort([8])
	g2 = merge_sort(a[3,9,10])
		g1 = merge_sort(a[3])
	       g2 = merge_sort(a[9,10])
			g1 =  merge_sort(a[9])
			g2 = merge_sort(a[10])
g2 = merge_sort(a[1,2,4,7,5])
	g1 = merge_sort(a[1,2])
		g1 = merge_sort([1])
		g2 = merget_sort([2])
	g2 = merge_sort(a[4,7,5])
		g1 = merge_sort(a[4])
	       g2 = merge_sort(a[7,5])
			g1 =  merge_sort(a[5])
			g2 = merge_sort(a[7])