Come implementare l'unione di due array ordinati in un array ordinato?

Per unire due array ordinati in uno solo ordinato, si può utilizzare un algoritmo di fusione simile a quello usato nel merge sort.

Idea:

• Scorrere entrambi gli array con due indici.
• Ad ogni passo, confrontare gli elementi correnti e aggiungere quello più piccolo all'array risultante.
• Quando uno dei due array termina, aggiungere gli elementi rimanenti dell'altro array.

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

    // Aggiungi gli elementi rimanenti
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Questo algoritmo funziona in tempo O(n + m), dove n e m sono le dimensioni degli array di input.