Wie kann man zwei sortierte Sequenzen so zusammenfügen, dass das Ergebnis sortiert bleibt?

Um zwei sortierte Sequenzen zu einer einzigen sortierten Sequenz zu verbinden, kann man den Merge-Algorithmus verwenden, der in linearer Zeit arbeitet.

Idee:

• Es gibt zwei sortierte Arrays oder Listen.
• Wir verwenden zwei Zeiger, einen für jedes Array.
• Wir vergleichen die aktuellen Elemente, das kleinere wird zum Ergebnis hinzugefügt und der entsprechende Zeiger verschoben.
• Wir wiederholen dies, bis beide Arrays durchlaufen sind.

Beispiel 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++
        }
    }
    // Füge die restlichen Elemente hinzu
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}