Как можете да обедините две сортирани последователности така, че резултатът да остане сортиран?

За да обедините две сортирани последователности в една сортирана, можете да използвате алгоритъма за сливане (merge), който работи в линейно време.

Идея:

• Има две сортирани масиви или списъка.
• Използваме два указателя, по един за всеки масив.
• Сравняваме текущите елементи, по-малкият добавяме към резултата и преместваме съответния указател.
• Повтаряме, докато не преминем и двата масива.

Пример на 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++
        }
    }
    // Добавяме останалите елементи
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}