Как слить два отсортированных массива в один отсортированный

Для слияния двух отсортированных массивов можно использовать алгоритм двух указателей. Создаем новый массив и поочередно добавляем в него меньший элемент из текущих позиций указателей.

fun mergeSortedArrays(arr1: IntArray, arr2: IntArray): IntArray {
    val merged = IntArray(arr1.size + arr2.size)
    var i = 0
    var j = 0
    var k = 0

    while (i < arr1.size && j < arr2.size) {
        merged[k++] = if (arr1[i] < arr2[j]) arr1[i++] else arr2[j++]
    }

    while (i < arr1.size) merged[k++] = arr1[i++]
    while (j < arr2.size) merged[k++] = arr2[j++]

    return merged
}

Сложность алгоритма - O(n+m), где n и m - длины массивов. Это оптимальное решение для данной задачи.