Cum se implementează combinarea a două array-uri sortate într-unul singur sortat?

Pentru a uni două array-uri sortate într-unul singur sortat, se poate folosi un algoritm de îmbinare similar cu cel utilizat în sortarea prin îmbinare (merge sort).

Ideea:

• Parcurgeți ambele array-uri cu doi indici.
• La fiecare pas, comparați elementele curente și adăugați cel mai mic în array-ul rezultat.
• Când unul dintre array-uri se termină, adăugați elementele rămase ale celuilalt array.

Exemplu în Go:

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++
        }
    }

    // Adăugați elementele rămase
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Acest algoritm funcționează în timp O(n + m), unde n și m sunt dimensiunile array-urilor de intrare.