Qo'shima xotira yordamida ikkita tartiblangan massivni yangi tartiblangan massivga qanday birlashtirish mumkin?

Ikki tartiblangan massivlarni qo'shish uchun qo'shimcha xotira bilan yangi tartiblangan massivga birlashtirish uchun, birlashish (merge) algoritmidan foydalanish mumkin, bu birlashish bo'yicha qadamga o'xshaydi.

G'oya:

1. Asl massivlarning o'lchamlarining yig'indisiga teng bo'lgan yangi massiv yarating.
2. Har biri uchun ikkita ko'rsatkichdan foydalaning.
3. Ikkala massivning hozirgi elementlarini solishtiring, kichikroq elementni yangi massivga qo'shing va mos ko'rsatkichni harakatlantiring.
4. Bir massiv tugagach, ikkinchi massivning qolgan elementlarini qo'shing.

Kotlin (Android) misoli:

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
}

Ushbu algoritm, massivlarning o'lchamlariga bog'liq holda, O(n + m) vaqt ichida ishlaydi va yangi massiv uchun qo'shimcha xotira talab qiladi.