Comment peut-on fusionner deux séquences triées de manière à ce que le résultat reste trié?

Pour fusionner deux séquences triées en une seule triée, on peut utiliser l'algorithme de fusion (merge), qui fonctionne en temps linéaire.

Idée :

• Il y a deux tableaux ou listes triés.
• On utilise deux pointeurs, un pour chaque tableau.
• On compare les éléments actuels, le plus petit est ajouté au résultat et on déplace le pointeur correspondant.
• On répète jusqu'à ce que les deux tableaux soient parcourus.

Exemple en 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++
        }
    }
    // Ajout des éléments restants
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}