[7급 국가직 자료구조론 2024년 8번]

다음은 병합 정렬(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]

(가) (나)