[파이썬] 병합정렬

• 왼쪽, 오른쪽 자식들이 할일 모두 끝마친 후에야 자신이 본연의 일을 수행하는 후위 수행 방식으로 진행

• 앞에서 했던 리스트 합치기 문제와 비슷

• p1을 lt, p2를 mid+1로 해서 작은 애를 먼저 tmp에 넣어주고
  작은 애가 p1 이면 p1+1을, p2면 p2+1을 해주면 됨

#병합정렬
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]
       if p2<=rt : tmp=tmp+arr[p2:rt+1]
       for i in range(len(tmp)) :
            arr[lt+i]=tmp[i]

if __name__=='__main__' :
    arr=[23,11,45,36,15,67,33,21]
    print('before sort : ' , end='')
    print(arr)
    dsort(0,7) #divide sort의 약자, 분할한 다음에 정렬,0번부터 7번까지 정렬하라
    print()
    print('after sort : ', end='')
    print(arr)
    #dsort 함수는 lt부터 rt까지의 영역을 두개의 영역으로 나누는 작업
    #자기 영역을 무조건 절반으로 나누고