Merge Sort

import random

def mergeSort(p, r, arr):
    if p < r:
        q = int((p + r) / 2)
        mergeSort(p, q, arr)
        mergeSort(q + 1, r, arr)
        merge(p, q + 1, r, arr)


def merge(p, q, r, arr):
    temp_p, temp_q = p, q

    merged_list = []

    while temp_p < q or temp_q <= r:
        if temp_p == q:
            merged_list.append(arr[temp_q])
            temp_q += 1
            continue
        elif temp_q > r:
            merged_list.append(arr[temp_p])
            temp_p += 1
            continue
        elif arr[temp_p] < arr[temp_q]:
            merged_list.append(arr[temp_p])
            temp_p += 1
            continue
        else:
            merged_list.append(arr[temp_q])
            temp_q += 1
            continue

    for i in merged_list:
        arr[p] = i
        p += 1
    #print(p, q, r, arr, merged_list)

max_size = 10

M = [random.randint(0, 100) for _ in range(max_size)]

print(M)
mergeSort(0, max_size - 1, M)
print(M)

일단 개념을 들어보고 나름 생각나는대로 구현한 코드

 

def merge(A, p:int, q:int, r:int):
	i = p; j = q+1; t = 0
	tmp = [0 for i in range(len(A))]
	while i <= q and j <= r:
		if A[i] <= A[j]:
			tmp[t] = A[i]; t += 1; i += 1
		else:
			tmp[t] = A[j]; t += 1; j += 1
	while i <= q:
		tmp[t] = A[i]; t += 1; i += 1
	while j <= r:
		tmp[t] = A[j]; t += 1; j += 1
	i = p; t = 0
	while i <= r:
		A[i] = tmp[t]; t += 1; i += 1

이건 교수님이 올려주신 Merge 함수 코드.

 

나는 반복문에서 If를 4번 사용했는데, 어짜피 반복문에 if가 포함되므로 반복문 4번도 좋은 것 같다는 생각이 들었다...