Kuidas rakendada kahe sorteeritud massiivi ühendamist ühte sorteeritud massiivi?

Selleks, et ühendada kaks sorteeritud massiivi üheks sorteeritud massiiviks, saab kasutada ühendamise algoritmi, mis sarnaneb merge sort (ühendamise sorteerimine) algoritmile.

Idee:

• Läbida mõlemat massiivi kahe indeksiga.
• Iga sammu juures võrrelda praeguseid elemente ja lisada väiksem tulemusi massiivi.
• Kui üks massiividest lõpeb, lisada ülejäänud teise massiivi elemendid.

Näide Go keeles:

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

    // Lisada ülejäänud elemendid
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

See algoritm töötab ajaga O(n + m), kus n ja m on sisendmassiivide suurused.