[알고리즘] 분할 정복 - 합병 정렬, 제자리 정렬 (Divide and Conquer - Merge Sort, In-place Sort)

앞선 시간에 merge sort에 대해 설명 드렸습니다.

이번에는 in-place 정렬로 merge sort하는 법을 보여드리겠습니다.

 

1. 코드

 

n = int(input())
S = list(map(int, input().split()))


def mergesort(low, high):
    # 두 개로 분할함
    if low < high:
        mid = (low + high) // 2
        mergesort(low, mid)
        mergesort(mid+1, high)
        merge(low, mid, high)


def merge(low, mid, high):
    # 병합함
    i = low; j = mid + 1;
    U = list()
    while i <= mid and j <= high:
        #U.append(S[i] if S[i] < S[j] else S[j])
        #if S[i] < S[j]: i += 1
        #else: j += 1
        U.append((S[i], i := i + 1)[0] if S[i] < S[j] else (S[j], j := j + 1)[0])

    if i > mid:
        while j <= high:
            U.append(S[j])
            j += 1
    else:
        while i <= mid:
            U.append(S[i])
            i += 1

    for idx in range(low, high + 1):
        S[idx] = U[idx - low]


mergesort(0, n-1)
print(S)

 

감사합니다.

 

 

지적 환영합니다.