Kā īstenot divu sakārtotu masīvu apvienošanu vienā sakārtotā masīvā?

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 apvienošanas šķirošanā (merge sort).

Ideja:

• Pārlūkot abus masīvus ar diviem indeksiem.
• Katrā solī salīdzināt pašreizējos elementus un pievienot mazāko rezultāta masīvam.
• Kad viens no masīviem beidzas, pievienot pārējos elementus no otra masīva.

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 pārējos elementus
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Šis algoritms darbojas laikā O(n + m), kur n un m ir ievades masīvu izmēri.