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

1. Merge Sort의 알고리즘 및 코드

 

Problem : n개의 원소를 가지고 있는 정렬되지 않은 리스트 S를 오름차순으로 정렬

input : n과 정렬되지 않은 리스트 S

output : 정렬된 리스트 S

 

Merge Sort의 알고리즘)

1. 배열을 반으로 분할한다.

2. 분할한 배열을 정렬한다 (배열에 원소가 2개 이상이면 merge sort를 재귀 호출하여 정렬한다)

3. 분할한 배열을 합병하여 정렬한다.

 

그러면 결국엔 정렬은 배열에 원소가 1개 일 때 일어나겠죠? 근데 원소가 하나밖에 없으면 정렬할 필요가 없습니다.

따라서 merge sort는 배열의 원소가 하나가 될 때까지 쪼개고, 쪼개진 그 배열을 정렬하면서 합병하는 알고리즘이라 볼 수 있겠습니다.

 

 

그러면 한 번 코드로 작성해보겠습니다.

 

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


def mergesort(s, n):
    # 두 개로 분할함
    if len(s) > 1:
        # 원소가 2개 이상일 때, merge sort를 함
        m = n // 2      # m은 중간 인덱스
        h = n - m       # h는 중간 인덱스 이후의 시작 인덱스
        sub_a = s[:m]
        sub_b = s[m:]
        mergesort(sub_a, m)
        mergesort(sub_b, h)
        merge(s, sub_a, sub_b, m, h)


def merge(s, sub_a, sub_b, m, h):
    # 병합함
    i = j = k = 0
    while i < m and j < h:
        # 배열 안에서 합병과 정렬을 같이 함
        if sub_a[i] < sub_b[j]:
            s[k] = sub_a[i]
            i += 1
        else:
            s[k] = sub_b[j]
            j += 1
        k += 1

    if i > m:
        # 아직 남아 있는 배열이 있으면
        while j < h:
            s[k] = sub_b[j]
            j += 1; k += 1
    else:
        while i < m:
            s[k] = sub_a[i]
            i += 1; k += 1


mergesort(S, n)
print(S)

---

2. 시간 복잡도 분석, 공간 복잡도 분석

 

우선 merge 함수의 시간 복잡도를 보겠습니다.

basic operation은 sub_a[i] < sub_b[j], 즉 비교 연산을 하겠습니다.

 

이때 일정 시간 복잡도는 맞지 않으므로 worst-case에 대해 알아보겠습니다.

만약 sub_a = [2, 4], sub_b = [1, 3, 5] 이면 비교 연산은 2 + 3 - 1번 합니다.

 

이때 2는 sub_a의 길이, 3은 sub_b의 길이이므로 h + m - 1이라 봐도 무방합니다.

따라서 \(W(h, m)\,=\,h+m-1\)이라고 할 수 있겠네요.

 

하지만 이때, h + m = n 이므로 \(W(h,m)\,=\,n\) 이라 볼 수 있겠습니다!

 

그 다음으로는 merge sort 함수의 시간 복잡도를 보겠습니다.

 

\(W(n)\,=\,W(h)+W(m) + h + m -1\)입니다.

뒤의 h+m-1은 merge할 때의 시간 복잡도입니다.

 

만약 n이 2의 거듭제곱 수라고 가정하면,

\(W(n)\,=\,2W(\frac{n}{2}) + n - 1\) 이 되겠네요.

즉 \(W(n)\,=\,nlgn - (n-1)\)이 됩니다.

 

결론적으로 이 알고리즘은 \(\Theta(n lg n)\)이네요.

 

 

이 다음은 공간 복잡도를 보겠습니다.

 

보시다시피 sub_a, sub_b를 추가로 생성함으로써, 약 n개의 추가적인 공간을 더 쓰고 있습니다.

 

in-place 정렬이란 추가적인 공간 없이 제자리에서 정렬할 수 있는 기법을 말합니다.

위의 알고리즘은 약 2n개의 공간을 쓰고 있으므로 in-place 정렬이 아닙니다.

 

하지만 이를 in-place 정렬로 바꿀 수 있습니다.

 

다음 글에서 소개드리겠습니다.

감사합니다.

 

 

 

지적 환영합니다.