İki sıralı diziyi ek hafıza kullanarak yeni sıralı bir diziye nasıl birleştirebilirsiniz?

İki sıralanmış diziyi ek hafıza kullanarak yeni sıralanmış bir diziye birleştirmek için, birleştirme (merge) algoritması uygulanabilir, bu da sıralama ile birleştirme adımına benzer.

Fikir:

1. Her iki dizinin toplam boyutuna eşit olan yeni bir dizi oluşturun.
2. Her biri için birer gösterge kullanın.
3. Her iki dizinin mevcut öğelerini karşılaştırın, en küçüğü yeni diziye ekleyin ve ilgili göstergeyi hareket ettirin.
4. Bir dizinin sonuna gelindiğinde, diğer dizinin kalan öğelerini ekleyin.

Kotlin (Android) örneği:

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 algoritma, dizilerin boyutlarına bağlı olarak O(n + m) sürede çalışır ve yeni dizi için ek hafıza kullanır.