Merge sort 알고리즘의 버그 고치기

merge sort 알고리즘으로 숫자 리스트를 정렬하는 프로그램이 주어졌습니다. merge_sort() 함수를 테스트해 보니 코드가 올바르지 않다는 것을 알게 되었어요. 알고리즘이 제대로 동작하도록 코드를 수정해 보시겠어요?

이 연습은 강의의 일부입니다

Python으로 배우는 자료구조와 알고리즘

강의 보기

연습 안내

왼쪽 절반을 할당할 때의 실수를 수정하세요.
오른쪽 절반을 할당할 때의 실수를 수정하세요.
왼쪽 절반의 포인터를 업데이트할 때의 실수를 수정하세요.
오른쪽 절반의 포인터를 업데이트할 때의 실수를 수정하세요.

실습형 인터랙티브 연습

이 예제를 이 샘플 코드를 완성하여 풀어보세요.

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
        
        merge_sort(left_half)
        merge_sort(right_half)
 
        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
        		# Correct mistake when assigning left half
                my_list[k] = right_half[i]                
                i += 1
            else:
                # Correct mistake when assigning right half
                my_list[k] = left_half[j]
                j += 1
            k += 1
            
        while i < len(left_half):
            my_list[k] = left_half[i]
            # Correct mistake when updating pointer for left half
            j += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            # Correct mistake when updating pointer for right half
            i += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

코드 편집 및 실행