Hoe implementeer je het samenvoegen van twee gesorteerde arrays in één gesorteerde array?

Om twee gesorteerde arrays samen te voegen tot één gesorteerde array, kan een merge-algoritme worden gebruikt dat vergelijkbaar is met dat in merge sort.

Idee:

• Loop door beide arrays met twee indices.
• Vergelijk bij elke stap de huidige elementen en voeg de kleinste toe aan de resulterende array.
• Wanneer een van de arrays eindigt, voeg dan de resterende elementen van de andere array toe.

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

    // Voeg de resterende elementen toe
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Dit algoritme werkt in O(n + m) tijd, waarbij n en m de groottes van de invoerarrays zijn.