[알고리즘] 병합정렬

5. 병합정렬

퀵정렬과 마찬가지로 분할정복을 사용하는 정렬이며, 시간복잡도 역시 O(N*logN)이다.

퀵정렬은 data정렬이 어느정도 되어있는 상태에서 활용할 경우 가장 빠르고 강력하지만, pivot 값이 달라짐에 따라 분할되는 부분집합도 달라지므로 pivot 편증정도에 따라 시간복잡도가 최악이 될 수도 있다(시간 복잡도가 보장되지 않는다).

이에 반해 병합정렬은 최악의 경우에도 시간복잡도가 O(N*logN)을 보장한다.

병합정렬은 pivot값 설정없이 반절씩 나누면서 진행하므로 시간복잡도 측면에서 보장가능하다.

5-1. 분할 후 병합

pivot없이 N/2씩 분할하고, 분할이 더이상 되지 않을 때 2의배수(2, 4, ...)로 분할된 부분집합들을 순차적으로 병합(merge)한다.

분할한 후 병합을 할 때 정렬을 하면서 병합하고, 다시 말해 정렬이 된 상태에서 병합을 진행하기 때문에 시간복잡도가 제곱에 비례하진 않는다.

예를 들어 2개의 부분집합을 1개로(4개 원소, 5 6 7 8) 병합할때 이미 정렬되어있는 첫번째 부분집합(6, 7)과 두번째 부분집합(5, 8)의 첫번째 인덱스(6 - 5, 6 - 8, ...)부터 순차적으로 비교하면서 하나의 집합으로 병합하는 과정을 진행한다.

5-2. 파이썬 코드

분할하는 함수와 병합하는 함수를 나누어 구현하고, 분할하는 함수를 재귀호출 및 병합함수를 호출하는 방법을 이용하여 구현한다.

import sys
sys.setrecursionlimit(10**7)

array = [3, 10, 5, 1, 7, 6, 4, 2, 8, 9]
arrayLength = len(array)
result = []

#병합
def merge(start, middle, end):
    #부분집합1
    i = start
    #부분집합2
    j = middle + 1
    #병합된 집합(=i)
    k = start

    ##부분집합이 분할된 상태에서 병합하는 과정
    while i <= middle and j <= end:
        if array[i] <= array[j]:
            result[k] = array[i]
            i = i+1
        else:
            result[k] = array[j]
            j = j+1
        k = k+1
        print(result)

        ## i, j가 먼저 도달할경우 다른 부분집합의 원소를 그대로 병합해준다
        if i > middle:
            for t in range(j, end):
                result[k] = array[t]
                k = k+1
        else:
            for t in range(i, middle):
                result[k] = array[t]
                k = k+1


#분할
def mergeSort(start, end):
    if start <= end:
        middle = (start + end)/2
        mergeSort(start, middle)
        mergeSort(middle+1, end)
        merge(start, middle, end)


#함수호출
mergeSort(0, arrayLength-1)
print(result)