Эки сорттолгон массивти бириктирүүнүн жолдору кандай?

Ике сортталган массивди бириктирүү үчүн, бириктирүү алгоритмин колдонсо болот, ал 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 кирүү массивдеринин өлүшү.