Kā apvienot divus sakārtotus masīvus vienā, saglabājot elementu kārtību?

Lai apvienotu divus sakārtotus masīvus vienā sakārtotā masīvā, var izmantot apvienošanas algoritmu, kas līdzīgs tam, kas tiek izmantots sakārtošanā ar apvienošanu (merge sort). Ideja ir vienlaicīgi pārlūkot abus masīvus, salīdzinot pašreizējos elementus un pievienojot mazāko no tiem rezultāta masīvam.

Piemērs Go valodā:

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

    // Pievienot atlikušos elementus
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Šī metode darbojas laikā O(n + m), kur n un m ir sākotnējo masīvu izmēri.