Əlavə yaddaş istifadə edərək iki sıralanmış massivləri necə birləşdirmək olar?

İki sıralanmış massivləri əlavə yaddaş istifadə edərək yeni sıralanmış massivə birləşdirmək üçün, merge (birleştirme) algoritmindən istifadə etmək mümkündür, bu da merge sort-un bir addımına bənzəyir.

Fikir:

1. Hər iki orijinal massivlərin cəm ölçüsünə bərabər olan yeni bir massiv yaradın.
2. Hər biri üçün iki göstərici istifadə edin.
3. Hər iki massivdəki cari elementləri müqayisə edin, kiçik olanı yeni massivə əlavə edin və müvafiq göstəricini hərəkət etdirin.
4. Bir massiv bitdikdə, digər massivdə qalan elementləri əlavə edin.

Kotlin (Android) nümunəsi:

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
}

Bu algoritm, massivlərin ölçülərinə bağlı olaraq, O(n + m) vaxtda işləyir və yeni massiv üçün əlavə yaddaş istifadə edir.