Merge Sort (병합 정렬)

Merge Sort는 전형적인 분할 정복(divide and conquer) 알고리즘의 하나입니다. 시간복잡도 O(n^2)을 가지는 일반적인 정렬과 달리 Merge Sort의 시간 복잡도는 O(nlog_2 n) 이 됩니다.

 

1. 이등분씩 나누는 것을 반복해서 최소 단위까지 분할합니다. (divide)
2. 분할한 부분 리스트를 정렬합니다. (conquer)
3. 정렬된 부분 리스트들을 하나의 리스트에 병합합니다. (combine)

 

 

 

다음은 swift 언어로 구현한 divide, merge 메서드 입니다.

 

func divide(_ start: Int,_ end: Int) {
    if start >= end { return }
    let mid = (start + end) / 2

    divide(start, mid)
    divide(mid+1, end)

    merge(start, end)
}


func merge(_ start: Int,_ end: Int) {
    let mid = (start + end) / 2
    var i = start // left index
    var j = mid + 1 // right index
    var k = start // result index

    while i <= mid && j <= end {
        if arr[i] < arr[j] {
            result[k] = arr[i]
            i += 1
        } else {
            result[k] = arr[j]
            j += 1
        }
        k += 1
    }

    if i > mid { // 왼쪽만 다 정렬하고 오른쪽 리스트가 남은 경우
        while j <= end {
            result[k] = arr[j]
            k += 1
            j += 1
        }
    } else {
        while i <= mid {
            result[k] = arr[i]
            k += 1
            i += 1
        }
    }

    // 다시 원래 배열에 옮겨 담아요.
    for idx in start ... end {
        arr[idx] = result[idx]
    }
}

 

 

실행할 때는 divide(0, arr.count - 1)로 실행하면 됩니다.

이때 실행 과정을 살펴보면 아래와 같습니다.

divide(0, 7)
    mid = 3
    divide(0, 3)
        mid = 1
        divide(0, 1)
            mid = 0
            divide(0, 0)
            divide(1, 1)
            merge(0, 1)
        divide(2, 3)
            mid = 2
            divide(2, 2)
            divide(3, 3)
            merge(2, 3)
        merge(0, 3)
    divide(4, 7)
        mid = 5
        divide(4, 5)
            mid = 4
            divide(4, 4)
            divide(5, 5)
            merge(4, 5)
        divide(6, 7)
            mid = 6
            divide(6, 6)
            divide(7, 7)
            merge(6, 7)
        merge(4, 7)
    merge(0, 7)

 

 

 

알고리즘 - 병합 정렬(Merge Sort, 머지 소트)의 개념과 문제 활용법