Kako implementirati spajanje dve sortirane nizove u jedan sortirani niz?

Za spajanje dva sortirana niza u jedan sortirani niz, možete koristiti algoritam spajanja sličan onom koji se koristi u sortiranju spajanjem (merge sort).

Ideja:

• Proći kroz oba niza sa dva indeksa.
• Na svakom koraku, uporediti trenutne elemente i dodati manji u rezultujući niz.
• Kada jedan od nizova završi, dodajte preostale elemente drugog niza.

Primer u 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++
        }
    }

    // Dodajte preostale elemente
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Ovaj algoritam radi u vremenu O(n + m), gde su n i m veličine ulaznih nizova.