Merge sort

Merge Sort(합병정렬)

• 문제 : n개의 키를 내림차순으로 정렬
• 입력 : 정수 n, S[1...n]
• 출력 : 내림차순으로 정렬된 키를 가지고 있는 배열 S
• 2개의 배열을 하나로 만들기
• 공간복잡도 : Θ(n)

 

Merge

• 2개의 배열을 하나의 배열로 만들기
• 입력 : subarray S[low...high], low, mid, high
• 출력 : S[1...high]
• 기억공간 사용하지 않음

def mergesort(S, low, high) : 
    if low < high :
        mid = (low+high) // 2
        mergesort(S, low, mid)
        mergesort(S, mid + 1, high)
        merge(S, low, mid, high)

def merge(S, low, mid, high) : 
    i = low
    j = mid + 1
    k = low
    U = []
    while i <= mid and j <= high :
        if S[i] < S[j] :
            U[k] = S[i]
            ++i
        else : 
            U[k] = S[j]
            ++j
        ++k
    if i > mid :
        n = k
        for num in range(j, high) : 
            U[n] = S[num]
            ++n
    else : 
        n = k
        for num in range(i, mid) : 
            U[n] = S[num]
    for num in range(low, high) : 
        S[num] = U[num]