Πώς υλοποιείται η συγχώνευση δύο ταξινομημένων πινάκων σε έναν ταξινομημένο πίνακα;

Για να συγχωνεύσετε δύο ταξινομημένους πίνακες σε έναν ταξινομημένο πίνακα, μπορείτε να χρησιμοποιήσετε έναν αλγόριθμο συγχώνευσης που μοιάζει με αυτόν που χρησιμοποιείται στην ταξινόμηση συγχώνευσης (merge sort).

Ιδέα:

• Διασχίστε και τους δύο πίνακες με δύο δείκτες.
• Σε κάθε βήμα, συγκρίνετε τα τρέχοντα στοιχεία και προσθέστε το μικρότερο στον τελικό πίνακα.
• Όταν ένας από τους πίνακες τελειώσει, προσθέστε τα υπόλοιπα στοιχεία του άλλου πίνακα.

Παράδειγμα σε 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++
        }
    }

    // Προσθέστε τα υπόλοιπα στοιχεία
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Αυτός ο αλγόριθμος λειτουργεί σε χρόνο O(n + m), όπου n και m είναι τα μεγέθη των εισερχόμενων πινάκων.