[CS] 알고리즘 05 : 병합 정렬 (Merge Sort)

병합 정렬 (Merge Sort)

병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식으로 동작합니다. 이 과정은 재귀적으로 구현됩니다.

병합 정렬의 동작과정

병합 정렬의 시간복잡도

선택 정렬의 시간복잡도는 O(NlogN)이다.
분할 과정이 한 번 시행할 때마다 리스트의 크기가 1/2씩 감소하기 때문이다.

병합 정렬 코드 (Swift)

func mergeSort(_ arr: [Int]) -> [Int] {
    if arr.count <= 1 { return arr }
    
    let mid = arr.count / 2
    let leftArr = Array(arr[0..<mid])
    let rightArr = Array(arr[mid..<arr.count])
    
    let sortedLeftArr = mergeSort(leftArr)
    let sortedRightArr = mergeSort(rightArr)
    
    return merge(sortedLeftArr, sortedRightArr)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var left = left
    var right = right
    var res: [Int] = []
    
    while !left.isEmpty && !right.isEmpty {
        if left[0] < right[0] {
            res.append(left.removeFirst())
        } else {
            res.append(right.removeFirst())
        }
    }
    
    if !left.isEmpty {
        res.append(contentsOf: left)
    }
    
    if !right.isEmpty {
        res.append(contentsOf: right)
    }
    return res
}

let arr = [8, 3, 4, 7, 1, 5, 9, 2]
print(mergeSort(arr))