합병정렬 알고리즘(Merge Sort)

• 분할 정복 알고리즘이며, 안정적인 정렬이서 최악, 최선의 경우에도 시간복잡도는 N * log N를 갖는다.
• 합병정렬은 추가적인 메모리가 필요하다는 단점이 있다.
• 보통 재귀 함수로 구현한다.

과정

[ 5, 1, 2, 8, 7, 3, 9, 6, 10, 4 ]

1. 리스트의 같은 깊이의 나눠지지 않을 때까지 반을 나눈다.
2. 병합하면서 비교 정렬을 한다.
3. 정렬하면서, 어느 한쪽을 모두 비교했으면, 남은 쪽 요소를 붙인다.

예제

[ 5 ][ 1 ] [ 2 ][ 8 ] [ 7 ][ 6 ] [ 10 ][ 4 ]

[ 1 , 5 ][ 2 , 8 ] [ 6 , 7 ][ 4 , 10 ]

[ 1 , 2 , 5 , 8 ][ 4 , 6 , 7 , 10 ]

[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ]

알고리즘 구현

subSorted = list() #전역변수

def merge(array, left, middle, right):
    
    
    start1 = left
    start2 = middle + 1
    
    subSortedIdx = left
    
    #array 합병
    while start1 <= middle and start2 <= right:
        if array[start1] <= array[start2]:
            subSorted[subSortedIdx] = array[start1]
            subSortedIdx += 1
            start1 += 1
        else:
            subSorted[subSortedIdx] = array[start2]
            subSortedIdx += 1
            start2 += 1
            
    #남은값 일괄 복사
    if start1 > middle:
        for idx in range(start2,right+1):
            subSorted[subSortedIdx] = array[idx]
            subSortedIdx += 1
    else:
        for idx in range(start1,middle+1):
            subSorted[subSortedIdx] = array[idx]
            subSortedIdx += 1
            
    for idx in range(0,right+1):
        array[idx] = subSorted[idx]

    return

def mergeSort(array, left, right):

    if(left>=right):
        return
    
    middle = int((left+right)/2)
    mergeSort(array,left,middle)
    mergeSort(array,middle+1,right)
    merge(array,left,middle,right)

시간 복잡도 O(N log N)

최대 깊이까지 나누어 비교하는데 LogN의 복잡도를 갖고, 비교정렬하는데 N번의 반복을 하므로, 최악이든 최선이든 N log N의 복잡도를 갖는다.
보통 추가적인 메모리가 사용되어 메모리가 적은 환경에서 사용하기에 부적합한 정렬 알고리즘에 속한다.