Ako implementovať zlúčenie dvoch zoradených polí do jedného zoradeného poľa?

Na zlúčenie dvoch zoradených polí do jedného zoradeného poľa môžete použiť algoritmus zlúčenia podobný tomu, ktorý sa používa v zoradení spojením (merge sort).

Idea:

• Prechádzať obe polia s dvoma indexami.
• Pri každom kroku porovnať aktuálne prvky a pridať menší do výsledného poľa.
• Keď jeden z poľ skončí, pridať zostávajúce prvky druhého poľa.

Príklad v 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++
        }
    }

    // Pridať zostávajúce prvky
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Tento algoritmus funguje v čase O(n + m), kde n a m sú veľkosti vstupných polí.