Hoe kunnen twee gesorteerde arrays worden samengevoegd tot één, terwijl de volgorde van de elementen behouden blijft?

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. Het idee is om beide arrays gelijktijdig te doorlopen, de huidige elementen te vergelijken en het kleinste ervan aan de resulterende array toe te voegen.

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
}

Deze methode werkt in O(n + m) tijd, waarbij n en m de groottes van de oorspronkelijke arrays zijn.