3중 병합 정렬 (3-way Merge Sort)

1. Introduction

3중 병합 정렬은 전체 리스트를 3단계로 나눠 분할 정복하는 merge sort의 variation이다.

2. Approach

다음 코드는 파이썬에서 구현한 3중 병합 정렬이다.

def threeWayMergeRun(arr, a, b):
    threeWaySplit(arr, a, b+1, arr[:])
    
def threeWaySplit(arr, low, high, clone):
        if high - low < 2:
            return
  
        mid1 = low + ((high - low) // 3)
        mid2 = low + 2 * ((high - low) // 3) + 1
  
        threeWaySplit(clone, low, mid1, arr)
        threeWaySplit(clone, mid1, mid2, arr)
        threeWaySplit(clone, mid2, high, arr)
  
        threeWayMerge(clone, low, mid1, mid2, high, arr)
  
def threeWayMerge(arr, low, mid1, mid2, high, clone):
        i = low
        j = mid1
        k = mid2
        l = low
  
        while ((i < mid1) and (j < mid2) and (k < high)):
            if arr[i] < arr[j]:
                if arr[i] < arr[k]:
                    clone[l] = arr[i]
                    l += 1
                    i += 1
                else:
                    clone[l] = arr[k]
                    l += 1
                    k += 1
            else:
                if arr[j] < arr[k]:
                    clone[l] = arr[j]
                    l += 1
                    j += 1
                else:
                    clone[l] = arr[k]
                    l += 1
                    k += 1
  
        while ((i < mid1) and (j < mid2)):
            if arr[i] < arr[j]:
                clone[l] = arr[i]
                l += 1
                i += 1
            else:
                clone[l] = arr[j]
                l += 1
                j += 1
  
        while ((j < mid2) and (k < high)):
            if arr[j] < arr[k]:
                clone[l] = arr[j]
                l += 1
                j += 1
  
            else:
                clone[l] = arr[k]
                l += 1
                k += 1
  
        while ((i < mid1) and (k < high)):
            if arr[i] < arr[k]:
                clone[l] = arr[i]
                l += 1
                i += 1
            else:
                clone[l] = arr[k]
                l += 1
                k += 1
  
        while i < mid1:
            clone[l] = arr[i]
            l += 1
            i += 1
  
        while j < mid2:
            clone[l] = arr[j]
            l += 1
            j += 1
  
        while k < high:
            clone[l] = arr[k]
            l += 1
            k += 1

3. Discussion

점화식을 따르면, 이론적으로는 $O(nlog_3\; n)$의 시간복잡도를 가지지만 merge 단계에서 많은 연산을 거치기 때문에 평범한 merge sort에 비해 성능이 빼어나지는 않다.