Как да реализираме сливането на два сортирани масива в един сортиран масив?

За обединяване на два сортирани масива в един сортиран масив може да се използва алгоритъм за сливане, подобен на този, който се използва в сортирането чрез сливане (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 са размерите на входните масиви.