How can two sorted sequences be merged so that the result remains sorted?

To merge two sorted sequences into one sorted sequence, you can use the merge algorithm, which operates in linear time.

Idea:

• You have two sorted arrays or lists.
• Use two pointers, one for each array.
• Compare the current elements, add the smaller one to the result, and move the corresponding pointer.
• Repeat until both arrays are processed.

Example 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++
        }
    }
    // Add remaining elements
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}