İki sıralı diziyi tek sıralı diziye birleştirmenin yolu nedir?

İki sıralanmış diziyi tek sıralanmış diziye birleştirmek için, birleştirme algoritması kullanılabilir; bu, birleştirme sıralaması (merge sort) algoritmasında kullanılan ile benzerdir.

Fikir:

• Her iki diziyi de iki indeksle dolaşmak.
• Her adımda, mevcut öğeleri karşılaştırmak ve en küçüğü sonuç dizisine eklemek.
• Bir dizinin sonuna gelindiğinde, diğer dizinin kalan öğelerini eklemek.

Go dilinde örnek:

func mergeSortedArrays(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0

    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }

    // Kalan öğeleri ekle
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Bu algoritma, giriş dizilerinin boyutlarına bağlı olarak O(n + m) zamanında çalışır.