다음은 병합 정렬(merge sort) 알고리즘을 구현한 파이썬 코드이… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

다음은 병합 정렬(merge sort) 알고리즘을 구현한 파이썬 코드이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
sorted = []

def merge_sort(arr, left, right):
    if left<right:
        middle=(left+right)//2
        merge_sort(arr, left, middle)
        merge_sort(arr, middle+1, right)
        merge(arr, left, middle, right)

def merge(arr, left, middle, right):
    global sorted
    i=left
    j=middle+1
    k=( (가) )
    while i<=middle and ( (나) ):
        if arr[i]<=arr[j]:
            sorted.insert(k, arr[i])
            i=i+1
        else:
            sorted.insert(k, arr[j])
            j=j+1
        k=k+1

    if i>middle:
        sorted[k:k+right-j+1]=arr[j:right+1]
    else:
        sorted[k:k+middle-i+1]=arr[i:middle+1]

    arr[left:right+1]=sorted[left:right+1]

left / j<=right

left / k<=right

middle / j<=right

middle / k<=right

(가)는 left, (나)는 j<=right이다.
병합 결과를 쓰는 위치 k는 마지막에 sorted[left:right+1]을 arr로 복사하므로 구간 시작인 left에서 출발해야 한다. 병합 반복은 왼쪽 구간(i<=middle)과 오른쪽 구간(j<=right)에 모두 원소가 남아 있는 동안만 비교한다.
left / k<=right 조합은 오른쪽 구간이 먼저 소진돼도 k<=right가 참이어서 비교가 계속되고 arr[j]가 구간 밖을 읽는다.
middle / j<=right 조합은 병합 결과가 구간 중간부터 기록되어 복사 범위 sorted[left:right+1]과 어긋난다.
middle / k<=right 조합은 시작 위치와 반복 조건이 모두 틀렸다.