Merge Sort

Merge Sort(병합 정렬)

• 두부분으로 쪼개는 작업을재귀적으로 반복한뒤 분리한 순서와 반대로 크기가 작은 값부터 병합해 나가는 분할정복 알고리즘
• 시간복잡도 O(nlogn)

Merge Sort(병합 정렬) 순서

1. 리스트를 반으로 나눈다(Divide)
2. 왼쪽 리스트와 오른쪽 리스트를 각각 정렬(Conquer)
3. 정렬된 두 리스트를 하나의 정렬된 리스트로 합병(Combine)

 

func mergeSort(_ list: [Int]) -> [Int] {
    if list.count <= 1 {
        return list
    }

    var left: [Int] = []
    var right: [Int] = []

    let mid = list.count / 2
    left += list[0..<mid]
    right += list[mid..<list.count]
    
    var leftList = mergeSort(left)
    var rightList = mergeSort(right)

    return merge(&leftList, &rightList)
}

func merge(_ left: inout [Int], _ right: inout [Int]) -> [Int] {
    var result: [Int] = []
    while !left.isEmpty && !right.isEmpty {
        let value = left[0] < right[0] ? left.removeFirst() : right.removeFirst()
        result += [value]
    }
    if !left.isEmpty {
        result += left
    }
    if !right.isEmpty {
        result += right
    }
  
    return result
}

mergeSort([3, 8, 4, 5, 1, 2]) // [1, 2, 3, 4, 5, 8]