Эки сорттолгон массивди кошумча эс тутумду колдонуп жаңы сорттолгон массивге кантип бириктирсе болот?

Эки сорттолгон массивди жаңы сорттолгон массивге кошуу үчүн кошумча эс тутум менен, бириктирүү (merge) алгоритмин колдонсо болот, ал сорттоо менен бириктирүү кадамына окшош.

Идея:

1. Эки оригинал массивдин өлчөмдөрүнүн жыйындысына барабар жаңы массив түзүңүз.
2. Ар бирине эки көрсөткүчтү колдонуңуз.
3. Эки массивдин учурдагы элементтерин салыштырып, кичүү элементти жаңы массивге кошуп, тиешелүү көрсөткүчтү жылдырыңыз.
4. Бир массив аяктагында, экинчи массивдин калган элементтерин кошуңуз.

Котлинде мисал (Android):

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

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

    while (i < arr1.size) {
        result[k++] = arr1[i++]
    }

    while (j < arr2.size) {
        result[k++] = arr2[j++]
    }

    return result
}

Бул алгоритм убакытта O(n + m) иштейт, анда n жана m массивдердин өлчөмдөрү, жана жаңы массив үчүн кошумча эс тутумду колдонуп жатат.