[Kotlin] 병합 정렬(Merge Sort)

병합 정렬

병합 정렬은 퀵 정렬과 동일하게 O(n*logn)의 시간 복잡도를 가지고 있습니다. 하지만 피벗 값에 따라서 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있는 퀵 정렬과는 다르게 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(n*logn)의 시간 복잡도를 가집니다.

병합 정렬은 단순히 생각하면, 하나를 반절로 분할한 후 계산하고 나중에 분할한 것들을 합치는 방법입니다.

예시

위의 그림처럼 단계별로 나눠지는 것을 볼 수 있습니다.
앞서 말한 하나를 반절로 분할하고 계산하는 과정을 거치고 있습니다.

1단계에서 2단계로 2단계로 3단계로 갈 동안 정렬이 되어집니다.

쉽게 말해 하나를 나누고 start에서 mid까지 정렬하고, mid에서 end까지 정렬한 뒤 합치는 것입니다.

코드

private lateinit var sortedArr: IntArray
private fun main() {
    val arr = intArrayOf(9,8,7,6,5)
    sortedArr = IntArray(arr.size)
    mergeSort(arr, 0, arr.lastIndex)
    println(arr.joinToString(" "))
}

private fun merge(arr: IntArray, start: Int, mid: Int, end: Int) {
    var (i, j, k) = intArrayOf(start, mid + 1, start)
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            sortedArr[k] = arr[i]
            i++
        } else {
            sortedArr[k] = arr[j]
            j++
        }
        k++
    }
    if (i > mid) {
        for (t in j..end) {
            sortedArr[k] = arr[t]
            k++
        }
    } else {
        for (t in i..mid) {
            sortedArr[k] = arr[t]
            k++
        }
    }

    for (t in start..end) arr[t] = sortedArr[t]
}

private fun mergeSort(arr: IntArray, start: Int, end: Int) {
    if (start < end) {
        val mid = (start + end) / 2
        mergeSort(arr, start, mid)
        mergeSort(arr, mid + 1, end)
        merge(arr, start, mid, end)
    }
}