Kaip įgyvendinti dviejų surūšiuotų masyvų sujungimą į vieną surūšiuotą masyvą?

Norint sujungti du surūšiuotus masyvus į vieną surūšiuotą masyvą, galima naudoti sujungimo algoritmą, panašų į tą, kuris naudojamas sujungimo rūšiavime (merge sort).

Idėja:

• Eiti per abu masyvus su dviem indeksais.
• Kiekvieno žingsnio metu palyginti esamus elementus ir pridėti mažesnį į rezultato masyvą.
• Kai vienas iš masyvų baigsis, pridėti likusius kito masyvo elementus.

Pavyzdys Go kalba:

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

    // Pridėti likusius elementus
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Šis algoritmas veikia laiku O(n + m), kur n ir m yra įvesties masyvų dydžiai.