• 데이터들을 분할하여 각자 정렬 후 병합하여 전체 정렬을 하는 방식
• 대용량 데이터 측면에서 효율적인 성능을 보이지만, 추가 메모리를 필요로 한다
• 시간 복잡도 : O(nlogn), 공간 복잡도 : O(n)

// 배열을 병합 정렬을 사용하여 정렬하는 함수
fun sort(arr: IntArray, l: Int, r: Int) {
    // 기준점보다 큰 경우, 분할 계속 실행
    if (l < r) {
        val m = (l + r) / 2  // 중간 지점 계산
        sort(arr, l, m)      // 왼쪽 부분 배열 정렬
        sort(arr, m + 1, r)  // 오른쪽 부분 배열 정렬
        merge(arr, l, m, r)  // 병합 실행
    }
}

// 두 부분 배열을 병합하는 함수
fun merge(arr: IntArray, l: Int, m: Int, r: Int) {
    val n1 = m - l + 1  // 왼쪽 배열의 크기
    val n2 = r - m      // 오른쪽 배열의 크기
    val L = IntArray(n1)  // 왼쪽 배열 생성
    val R = IntArray(n2)  // 오른쪽 배열 생성

    // 왼쪽 배열에 값 복사
    for (i in 0 until n1) {
        L[i] = arr[l + i]
    }
    // 오른쪽 배열에 값 복사
    for (j in 0 until n2) {
        R[j] = arr[m + 1 + j]
    }

    var i = 0 // 왼쪽 배열의 시작 인덱스
    var j = 0 // 오른쪽 배열의 시작 인덱스
    var k = l // 병합될 배열의 시작 인덱스

    // 두 배열의 요소를 비교하며 병합
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i]
            i++
        } else {
            arr[k] = R[j]
            j++
        }
        k++
    }

    // 남은 왼쪽 배열 요소들을 병합
    while (i < n1) {
        arr[k] = L[i]
        i++
        k++
    }
    // 남은 오른쪽 배열 요소들을 병합
    while (j < n2) {
        arr[k] = R[j]
        j++
        k++
    }
}