Como pode mesclar duas sequências ordenadas de modo que o resultado permaneça ordenado?

Para combinar duas sequências ordenadas numa única ordenada, pode usar o algoritmo de fusão (merge), que funciona em tempo linear.

Ideia:

• Existem dois arrays ou listas ordenadas.
• Usamos dois ponteiros, um para cada array.
• Comparamos os elementos atuais, o menor é adicionado ao resultado e deslocamos o ponteiro correspondente.
• Repetimos até percorrer ambos os arrays.

Exemplo em 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++
        }
    }
    // Adiciona os elementos restantes
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}