[정렬] 4.병합정렬(Merge sort)

들어가기 전에,

 

문제에서 주어진 '정렬할 대상의 갯수'가 커지면 정렬이 어렵다.

 

그것에 대한 해결책은? 

분할 정복 기법(Divide-and-Conquer)

STEP 1. 원래 문제를 독립적으로 풀 수 있는 작은 문제로 나눔(Divide)

STEP 2. 각각의 문제를 풂(Delegate)

STEP 3. 각각의 문제의 답을 이용해 원래 문제의 답을 만든다.(Combine)

 

정렬을 위한 분할 정복 기법은 대표적으로 두 가지가 있다.

1. 병합 정렬(Merge sort)

2. 퀵 정렬(Quick sort)

 

본격적으로 병합 정렬에 대해 알아보자.

알고리즘의 기본 아이디어

Divide - 정렬할 리스트를 앞 쪽 반, 뒤쪽 반으로 나눈다.

Half Delegate(Front) - 앞 쪽 반을 정렬한다.

Half Delegate(Back) - 뒤 쪽 반을 정렬한다.

Combine - 이 둘을 합쳐 하나의 정렬된 리스트를 만든다.

 

이 아이디어를 아래 그림과 같이 재귀적으로 진행한다.

병합 정렬 예시

 

---

병합정렬 Python Code

def merge(A, B):
    if(len(A) == 0):
        return B
    if(len(B) == 0):
        return A
    if(A[0] < B[0]):
        return [A[0]] + merge(A[1:], B)
    else:
        return [B[0]] + merge(A, B[1:])
        
def mergesort(L):
    if(len(L) == 1):
        return L
    return merge(mergesort(L[:int(len(L)/2)]), mergesort(L[int(len(L)/2):]))

 

 

입력 및 출력

---

병합 정렬의 시간 복잡도

점화식

T(n) = 2*T(n/2) + n, T(n) = Θ(nlogn)

즉, n/2개의 리스트 2개를 각각 정렬하고, 이를 합치는데 n번 비교

 

특징

1. 입력의 형태애 상관없이 언제나 같은 시간 복잡도를 보장한다.

2. 언제나 문제의 크기가 1/2로 줄어든다.

---

영상으로 어떻게 진행되는지 참고해보자.