[알고리즘] 병합정렬

문제

병합정렬을 반복 함수로 구현하라 (python)

소스코드

def merge_sort(x):

    list = []

    for i in range(len(x)):
        temp = [x[i]]
        list.append(temp)

    print("Original :",x)

    while(len(list) != 1):
        j = 0

        while(j < len(list)-1):
            tempList = merge(list[j], list[j+1])
            list[j] = tempList
            del list[j+1]
            j = j+1
        print("Steps :",list)

    print("MergeSort :",list[0])

def merge(a, b):
    sorted = []
    cnt1, cnt2 = 0, 0

    while((cnt1 < len(a)) and (cnt2 < len(b))):
        if(a[cnt1] > b[cnt2]):
            sorted.append(b[cnt2])
            cnt2 = cnt2 + 1

        elif(a[cnt1] < b[cnt2]):
            sorted.append(a[cnt1])
            cnt1 = cnt1 + 1

        elif(a[cnt1] == b[cnt2]):
            sorted.append(a[cnt1])
            sorted.append(b[cnt2])
            cnt1, cnt2 = cnt1 + 1, cnt2 + 1

    if(cnt1 < len(a)):
        for f in range(cnt1, len(a)):
            sorted.append(a[f])
    elif(cnt2 < len(b)):
        for k in range(cnt2, len(b)):
            sorted.append(b[k])

    return sorted

data=[27,10,12,20,25,13,15,22]
merge_sort(data)

실행 결과