Ինչպե՞ս կարելի է միացնել երկու դասավորված հաջորդականություններ այնպես, որ արդյունքը մնա դասավորված։

Երկու դասավորված հաջորդականությունները միացնելու համար, կարող եք օգտագործել միացման (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
}