package sprint3.k

/**
 * Принимает один массив и три целочисленных индекса: left, mid, и right.
 * Сливает две отсортированные части одного и того же массива в один отсортированный массив.
 * Первая часть массива определяется полуинтервалом [left, mid) массива array,
 * а вторая часть – полуинтервалом [mid, right) того же массива array.
 * @param arr - массив, состоящий из двух отсортированных частей.
 * @param left - начальный индекс левой отсортированной части массива.
 * @param mid - начальный индекс правой отсортированной части массива.
 * @param right - конечный индекс правой отсортированной части массива.
 * @return сливаемый массив.
 */
fun merge(arr: IntArray, left: Int, mid: Int, right: Int): IntArray {
    var l = left
    var r = mid
    var resultIndex = 0
    val result = arr.clone()
    while (l < mid && r < right) {
        if (arr[l] <= arr[r]) {
            result[resultIndex] = arr[l]
            l++
        } else {
            result[resultIndex] = arr[r]
            r++
        }
        resultIndex++
    }

    while (l < mid) {
        result[resultIndex] = arr[l]
        resultIndex++
        l++
    }
    while (r < right) {
        result[resultIndex] = arr[r]
        resultIndex++
        r++
    }
    return result
}

/**
 * Принимает некоторый подмассив, который нужно отсортировать. Подмассив задаётся полуинтервалом — его началом и концом.
 * Разбивает полуинтервал на две половинки и рекурсивно вызывает сортировку отдельно для каждой.
 * Затем два отсортированных массива сливаются в один с помощью [merge].
 * @param arr массив, который надо отсортировать
 * @param left индекс начала полуинтервала
 * @param right индекс конца полуинтервал
 */
fun merge_sort(arr: IntArray, left: Int, right: Int) {
    if (right - left <= 1) {
        return
    }
    val mid = (right - left) / 2
    if (left == mid) {
        return
    }


}

fun test() {
    val a = intArrayOf(1, 4, 9, 2, 10, 11)
    val b: IntArray = merge(a, 0, 3, 6)
    val expected = intArrayOf(1, 2, 4, 9, 10, 11)
    assert(b.contentEquals(expected))
    val c = intArrayOf(1, 4, 2, 10, 1, 2)
    merge_sort(c, 0, 6)
    val expected2 = intArrayOf(1, 1, 2, 2, 4, 10)
    assert(c.contentEquals(expected2))
}