합병 정렬 merge sort

분할 정복

분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

정복 : 각각의 작은 문제를 순환적으로 해결

합병 : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함

ALGORITHMS 이 단어를 반으로 쪼개고 

ALGOR  ITHMS devide

AGLOR  HIMST recursively sort 각각 정렬한 뒤

AGHILMORST merge 합병한다.

1,2,2,3,4,5,6,7

2,4,5,7     1,2,3,6

2,5 4,7     1,3 2,6

5 2 4 7 1 3 2 6

mergeSort(A,p,r):

  if p<r:

    q=(p+r)//2

    mergeSort(A,p,q)

    mergeSort(A,q+1,r)

    merge(A,p,q,r)

데이터가 n개 일 때 걸리는 시간

T(n) = T(n/2)+T(n/2)+n , n/2개를 mergesort하는데 걸리는 시간은 T(n/2)이고 병합하는 데 걸리는 시간은 n이다.

병합하는 각 단계마다 n시간이 걸리고 단계는 총 logn개이므로 O(n*logn)

arr = [3, 5, 1, 2, 9, 6, 4, 5, 7]
def mergeSort(arr):
    if len(arr)==1:return arr # 리스트의 길이가 1이면 정렬할 필요가 없으므로 리턴
    tmp=[]                    #이 빈 리스트에 정렬되는 원소가 삽입된다
    half=len(arr)//2          #중간 값을 구한다
    L=mergeSort(arr[:half])   #L은 왼쪽 정렬
    R=mergeSort(arr[half:])   #R은 오른쪽 정렬
    while len(L)>0 and len(R)>0: #L과 R에 원소가 남아있을 때
        if L[0]>R[0]:            #R의 값이 작다면
            tmp.append(R[0])     #R을 먼저 tmp에 삽입
            R.pop(0)             #R의 첫번째 값 삭제
        else:
            tmp.append(L[0])
            L.pop(0)
    if len(L)==0:tmp+=R          #L이 비었다면 R을 tmp에 붙인다. L이 비었다는 것은 R에 남아있는 값들이 tmp에 있는 값보다 크다는 의미이다. 
    if len(R)==0:tmp+=L
    return tmp
print(mergeSort(arr))

def mergeSort(arr,p,r):
    if p<r:
        q=(p+r)//2
        mergeSort(arr,p,q)
        mergeSort(arr,q+1,r)
        merge(arr,p,q,r)
def merge(arr,p,q,r):
    i=p
    j=q+1
    k=p
    tmp=[0]*len(arr)
    while i<=p and j<=r:
        if arr[i]<arr[j]:
            tmp[k]=arr[i]
            i+=1
        else:
            tmp[k]=arr[j]
            j+=1
        k+=1
    while i<=q:
        tmp[k]=arr[i]
        i+=1
        k+=1
    while j<=r:
        tmp[k]=arr[j]
        k+=1
        j+=1
    for i in range(p,r+1):
        arr[i]=tmp[i]
    print(arr)
mergeSort([4,3,2,1],0,3)