Jak zaimplementować scalanie dwóch posortowanych tablic w jedną posortowaną tablicę?

Aby scalić dwie posortowane tablice w jedną posortowaną tablicę, można użyć algorytmu scalania podobnego do tego stosowanego w sortowaniu przez scalanie (merge sort).

Pomysł:

• Przechodzić obie tablice z dwoma indeksami.
• Na każdym kroku porównywać bieżące elementy i dodawać mniejszy do tablicy wynikowej.
• Gdy jedna z tablic się skończy, dodać pozostałe elementy drugiej tablicy.

Przykład w 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++
        }
    }

    // Dodaj pozostałe elementy
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Ten algorytm działa w czasie O(n + m), gdzie n i m to rozmiary wejściowych tablic.