Чӣ гуна метавон ду массиви ба тартиб даровардашударо бо истифода аз ёддоштии иловагӣ ба массиви нав дароварда, ба тартиб даровардашудаи нав?

Барои пайваст кардани ду массиви ба ҳам рўйхатшуда ба массиви нав бо истифода аз хотираи иловагӣ, шумо метавонед алгоритми омезиш (merge)-ро истифода баред, ки монанд ба қадами аз сортировкаи омезишӣ мебошад.

Ният:

1. Массиве нав эҷод кунед, ки андозаи он баробар ба ҷамъияти андозаи ду массиви аслӣ мебошад.
2. Ду ишорагарро истифода баред, яке барои ҳар як массив.
3. Ҳангоми муқоиса кардани унсурҳои ҳозира, унсури хурдро ба массиви нав илова кунед ва ишорагарро ҳаракат диҳед.
4. Вақте ки яке аз массивҳо ба охир мерасад, унсурҳои боқимондаи дигарро илова кунед.

Масалан дар Kotlin (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 андозаи массивҳо мебошанд, ва барои массиви нав хотираи иловагӣ истифода мебарад.