Hogyan lehet két rendezett sorozatot összefűzni úgy, hogy az eredmény rendezett maradjon?

Két rendezett sorozat egyesítéséhez egy rendezett sorozatba, használhatjuk az összefésülés (merge) algoritmust, amely lineáris időben működik.

Ötlet:

• Két rendezett tömb vagy lista van.
• Két mutatót használunk, egyet mindegyikhez.
• Összehasonlítjuk a jelenlegi elemeket, a kisebbet hozzáadjuk az eredményhez, és a megfelelő mutatót léptetjük.
• Ezt ismételjük, amíg mindkét tömböt végig nem értük.

Kotlin példa:

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++
        }
    }
    // Hozzáadjuk a maradék elemeket
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}