Ikki tartiblangan ketma-ketlikni qanday birlashtirish mumkin, shunda natija tartibli qoladi?

Ikki tartiblangan ketma-ketlikni bir tartiblangan ketma-ketlikka birlashtirish uchun, birlashtirish (merge) algoritmidan foydalanish mumkin, u chiziqli vaqtda ishlaydi.

G'oya:

• Ikki tartiblangan massiv yoki ro'yxat mavjud.
• Har biri uchun ikki ko'rsatkichdan foydalanamiz.
• Hozirgi elementlarni solishtiramiz, kichigi natijaga qo'shiladi va mos keladigan ko'rsatkichni harakatlantiramiz.
• Ikkala massivni ham o'tguncha takrorlaymiz.

Kotlin misoli:

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++
        }
    }
    // Qolgan elementlarni qo'shish
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}