Hoe kunnen twee gesorteerde reeksen worden samengevoegd zodat het resultaat gesorteerd blijft?

Om twee gesorteerde reeksen samen te voegen tot één gesorteerde reeks, kan het merge-algoritme worden gebruikt, dat in lineaire tijd werkt.

Idee:

• Er zijn twee gesorteerde arrays of lijsten.
• We gebruiken twee pointers, één voor elk array.
• We vergelijken de huidige elementen, het kleinere wordt aan het resultaat toegevoegd en de bijbehorende pointer wordt verschoven.
• We herhalen dit totdat beide arrays zijn doorlopen.

Voorbeeld 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++
        }
    }
    // Voeg de resterende elementen toe
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}