[알고리즘] Merge Sort

정렬된 두 배열

 

merge_sort(num_list, start_idx, end_idx)

처음부터 끝 인덱스 까지는 0, len(num_list)-1

중간값 mid_idx = (start_idx + end_idx) // 2

 

start_idx < end_idx 일 때 :  merge_sort() 두번 호출하고, 합친다.

1. merge_sort(num_list, start_idx, mid_idx)

2. merge_sort(num_list, mid_idx+1, end_idx)

그리고  합친다! combine(num_list, start_idx, mid_idx, end_idx)

l_idx = start_idx  # start_idx ~ mid_idx

r_idx = mid_idx + 1 # mid_idx+1 ~ end_idx

 

l_idx <= mid_idx  and  r_idx <= end_idx인 동안 진행.

num_list[l_idx] < num_list[r_idx] 이면, 정렬된 리스트에 num_list[l_idx] 추가.