[알고리즘][KOTLIN] 합병 정렬 - O(nlogn)

합병 정렬

• 정의 : 분할정복과 비슷한 개념으로 주어진 배열을 더 이상 나눌 수 없을 때까지 쪼갠 후(Divide) 정렬하여 다시 쪼개진 요소들을 합친다(Conqurr).

코드

import java.io.*
import java.util.*

private lateinit var sorted: IntArray

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val st = StringTokenizer(br.readLine())
    sorted = IntArray(n)
    val numbers = IntArray(n) {
        st.nextToken().toInt()
    }

    mergeSort(numbers, 0, numbers.size - 1)

    for (num in numbers) {
        print("$num ")
    }
}

private fun mergeSort(arr: IntArray, left: Int, right: Int) {
    if (left == right) return

    val mid = (left + right) / 2
    mergeSort(arr, left, mid) // 주어진 배열을 가운데 기준으로 짜를 때 왼쪽 부분 리스트
    mergeSort(arr, mid + 1, right) // 주어진 배열을 가운데 기준으로 짜를 때 오른 쪽 부분 리스트
    merge(arr, left, mid, right)// 쪼개진 리스트를 정렬하여 병합
}

private fun merge(arr: IntArray, left: Int, mid: Int, right: Int) {
    var l = left // 왼쪽 부분 리스트 시작 위치
    var r = mid + 1 // 오른쪽 부분 리스트 시작 위치
    var idx = left // 새로운 배열에 넣을 위치

    while (l <= mid && r <= right) {
        // 정열 배열에 저장
        if (arr[l] <= arr[r]) {
            sorted[idx++] = arr[l++]
        } else {
            sorted[idx++] = arr[r++]
        }
    }

    // 왼쪽 부분 리스트에 더 이상 값이 없을 경우
    if (l > mid) {
        // 오른쪽 부분 리스트에 남은 것이 있으면 정열 배열에 저장
        while (r <= right) {
            sorted[idx++] = arr[r++]
        }
    } else {
        // 오른쪽 부분 리스트에 더 이상 값이 없을 경우
        while (l <= mid) {
            sorted[idx++] = arr[l++]
        }
    }

    // 정열 배열을 원래의 배열에 저장 함
    for (i in left..right) {
        arr[i] = sorted[i]
    }
}