İki sıralanmış ardıcıllığı necə birləşdirmək olar ki, nəticə sıralı qalsın?

İki sıralanmış ardıcıllığı bir sıralanmış ardıcıllığa birləşdirmək üçün, birləşmə (merge) algoritmindən istifadə etmək olar, bu, xətt vaxtında işləyir.

İdeya:

• İki sıralanmış massiv və ya siyahı mövcuddur.
• Hər biri üçün iki göstərici istifadə edirik.
• Mövcud elementləri müqayisə edirik, kiçik olan nəticəyə əlavə olunur və müvafiq göstərici irəli çəkilir.
• Hər iki massiv keçilənə qədər təkrarlayırıq.

Kotlin nümunəsi:

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++
        }
    }
    // Qalan elementləri əlavə et
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}