Cum se pot combina două secvențe sortate astfel încât rezultatul să rămână sortat?

Pentru a combina două secvențe sortate într-una singură sortată, se poate folosi algoritmul de fuziune (merge), care funcționează în timp liniar.

Ideea:

• Există două array-uri sau liste sortate.
• Se folosesc doi indicatori, câte unul pentru fiecare array.
• Se compară elementele curente, cel mai mic se adaugă în rezultat și se deplasează indicatorul corespunzător.
• Se repetă până când se parcurg ambele array-uri.

Exemplu în 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++
        }
    }
    // Adăugăm elementele rămase
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}