Wie man die Zusammenführung von zwei sortierten Arrays in ein sortiertes Array implementiert?

Um zwei sortierte Arrays zu einem sortierten Array zusammenzuführen, kann ein Merge-Algorithmus verwendet werden, der dem in der Mergesort (Merge Sort) verwendeten ähnelt.

Idee:

• Beide Arrays mit zwei Indizes durchlaufen.
• Bei jedem Schritt die aktuellen Elemente vergleichen und das kleinere in das Ergebnis-Array einfügen.
• Wenn eines der Arrays endet, die verbleibenden Elemente des anderen Arrays hinzufügen.

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

    // Restliche Elemente hinzufügen
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Dieser Algorithmus läuft in O(n + m) Zeit, wobei n und m die Größen der Eingabearrays sind.