병합 정렬 (합병 정렬, Merge Sort)

1. Introduction

병합 정렬은 프로그램 내장 방식으로 유명한 존 폰 노이만에 의해 제안된 정렬 알고리즘이다. 분할 정복법을 기반으로 하여 주어진 리스트를 분할하고 정렬하여 다시 병합한다.

병합 정렬은 최선, 최악, 평균 상황에서 항상 시간복잡도가 $O(nlog\; n)$임을 보장하며 stable한 알고리즘이다.

구현 방식에는 Top-down 방식과 Bottom-up 방식이 있다. 

2. Approach

다음 이미지는 병합 정렬의 과정을 보여준다. 출처는 위키피디아.

Animation of Merge Sort

 

다음 코드는 Top-down merge sort를 파이썬에서 구현한 것이다.

def topDownMergeRun(arr, a, b):
    clone = arr[a:b+1]
    topDownMerge(clone)
    arr[a:b+1] = clone

def topDownMerge(arr): 
    if len(arr) > 1: 
        mid = len(arr) // 2
        L = arr[:mid] 
        R = arr[mid:]
  
        topDownMerge(L) 
        topDownMerge(R) 
  
        i = j = k = 0
          
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+=1
            else: 
                arr[k] = R[j] 
                j+=1
            k+=1
          
        while i < len(L): 
            arr[k] = L[i] 
            i+=1
            k+=1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+=1
            k+=1

다음 코드는 Bottom-up merge sort를 파이썬에서 구현한 것이다.

def bottomUpMergeRun(arr, a, b):
    clone = arr[a:b+1]
    bottomUpMerge(clone)
    arr[a:b+1] = clone
    
def bottomUpMerge(arr):
    current_size = 1
    while current_size < len(arr) - 1: 
        left = 0
        while left < len(arr)-1: 
            mid = left + current_size - 1
            right = ((2 * current_size + left - 1, len(arr) - 1)[2 * current_size + left - 1 > len(arr)-1]) 
            merge(arr, left, mid, right) 
            left = left + current_size*2
        current_size = 2 * current_size 

def merge(a, l, m, r): 
    n1 = m - l + 1
    n2 = r - m 
    L = [0] * n1 
    R = [0] * n2 
    for i in range(0, n1): 
        L[i] = a[l + i] 
    for i in range(0, n2): 
        R[i] = a[m + i + 1] 
  
    i, j, k = 0, 0, l 
    while i < n1 and j < n2: 
        if L[i] > R[j]: 
            a[k] = R[j] 
            j += 1
        else: 
            a[k] = L[i] 
            i += 1
        k += 1
  
    while i < n1: 
        a[k] = L[i] 
        i += 1
        k += 1
  
    while j < n2: 
        a[k] = R[j] 
        j += 1
        k += 1

 

3. Discussion

병합 정렬의 아이디어는 외부 정렬 (External Sort)의 근간이 될 정도로 major한 알고리즘이다.

일정한 시간복잡도를 보장하지만 Auxiliary (보조배열)을 사용해야 한다는 단점이 있다. 이 때문에 callstack에 쌓이는 공간 외에도 $O(n)$의 공간을 추가로 사용한다.

물론 In-place하게 구현할 수는 있으나, 그 경우 시간복잡도가 $O(n^2)$이 된다. 다음 코드는 in-place merge sort를 파이썬에서 구현한 것이다.

def inPlaceMerge(arr, start, mid, end): 
    start2 = mid + 1
  
    if (arr[mid] <= arr[start2]): 
        return
      
    while (start <= mid and start2 <= end): 
  
        if (arr[start] <= arr[start2]): 
            start += 1
        else: 
            value = arr[start2]
            index = start2
  
            while (index != start): 
                arr[index] = arr[index - 1]
                index -= 1
              
            arr[start] = value
  
            start += 1
            mid += 1
            start2 += 1
          
def inPlaceMergeSort(arr, l, r): 
    if (l < r): 
        m = l + (r - l) // 2
        
        inPlaceMergeSort(arr, l, m)
        inPlaceMergeSort(arr, m + 1, r)
  
        inPlaceMerge(arr, l, m, r)