როგორ განვახორციელოთ ორი სორტირებული მასივის გაერთიანება ერთ სორტირებულ მასივში?

ორი სორტირებული მასივის გაერთიანებისთვის ერთ სორტირებულ მასივში, შეიძლება გამოიყენოს გაერთიანების ალგორითმი, რომელიც მსგავსია merge sort-ის (შერწყმის სორტირება) გამოყენებული ალგორითმის.

იდეა:

• ორივე მასივზე ორი ინდექსით გავლა.
• ყოველი ნაბიჯით, შედარება მიმდინარე ელემენტების და უმცირესის დამატება შედეგის მასივში.
• როდესაც ერთ-ერთი მასივი დასრულდება, დარჩენილი ელემენტები მეორე მასივიდან დამატება.

მაგალითი Go-ში:

func mergeSortedArrays(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0

    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }

    // დარჩენილი ელემენტების დამატება
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

ეს ალგორითმი მუშაობს დროით O(n + m), სადაც n და m არის შესვლის მასივების ზომები.