Hogyan valósítható meg két rendezett tömb egyesítése egy rendezett tömbbé?

Két rendezett tömb egyesítéséhez egy rendezett tömbbé, használhatunk egy összeolvasztási algoritmust, amely hasonló a merge sort (összefésüléses rendezés) során alkalmazott algoritmushoz.

Ötlet:

• Mindkét tömbön két index segítségével haladunk végig.
• Minden lépésben összehasonlítjuk a jelenlegi elemeket, és a kisebbet hozzáadjuk az eredmény tömbhöz.
• Amikor az egyik tömb véget ér, hozzáadjuk a másik tömbben maradt összes elemet.

Példa Go nyelven:

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

    // Maradék elemek hozzáadása
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Ez az algoritmus O(n + m) időben működik, ahol n és m a bemeneti tömbök mérete.