18. 병합정렬

병합정렬 메카니즘

def Dsort(lt, rt):
    if lt<rt:
        mid=(lt+rt)//2
        Dsort(lt, mid) #왼쪽자식
        Dsort(mid+1, rt) #오른쪽 자식
        #왼쪽자식 오른쪽자식의 일을 처리한 후에 본인(함수) 일을 후행한다.
        p1=lt
        p2=mid +1
        tmp=[]
        while p1<=mid and p2<=rt:
            if arr[p1]<arr[p2]:
                tmp.append(arr[p1]) #작은 값을 먼저 넣는다.
                p1+=1
            else:
                tmp.append(arr[p2]) #작은 값을 먼저 넣는다. 
                p2+=1
        if p1<=mid: tmp=tmp+arr[p1:mid+1]  #p1부터 mid까지 슬라이싱
        if p2<=rt: tmp=tmp+arr[p2:rt+1]    #p2부터 rt까지 슬라이싱 
        for i in range(len(tmp)):
            arr[lt+i]=tmp[i]



if __name__=="__main__":
    arr=[23, 11, 45, 36, 15, 67, 33, 21]
    print("Bofore sort : ", end='')
    print(arr)
    Dsort(0, 7)
    print()
    print("After sort : ", end='')
    print(arr)

 

Bofore sort : [23, 11, 45, 36, 15, 67, 33, 21]

 

After sort : [11, 15, 21, 23, 33, 36, 45, 67]

 

 

보충