Come si possono unire due sequenze ordinate in modo che il risultato rimanga ordinato?

Per unire due sequenze ordinate in una sequenza ordinata, si può usare l'algoritmo di fusione (merge), che funziona in tempo lineare.

Idea:

• Ci sono due array o liste ordinate.
• Usiamo due puntatori, uno per ciascun array.
• Confrontiamo gli elementi attuali, quello più piccolo viene aggiunto al risultato e spostiamo il puntatore corrispondente.
• Ripetiamo finché non attraversiamo entrambi gli array.

Esempio in Kotlin:

fun mergeSortedLists(a: List<Int>, b: List<Int>): List<Int> {
    val result = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < a.size && j < b.size) {
        if (a[i] <= b[j]) {
            result.add(a[i])
            i++
        } else {
            result.add(b[j])
            j++
        }
    }
    // Aggiungi gli elementi rimanenti
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}