Πώς μπορεί κανείς να ενώσει δύο ταξινομημένους πίνακες σε έναν νέο ταξινομημένο πίνακα, χρησιμοποιώντας επιπλέον μνήμη;

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

Ιδέα:

1. Δημιουργήστε έναν νέο πίνακα του μεγέθους ίσου με το άθροισμα των μεγεθών των δύο αρχικών πινάκων.
2. Χρησιμοποιήστε δύο δείκτες, έναν για κάθε πίνακα.
3. Συγκρίνετε τα τρέχοντα στοιχεία και των δύο πινάκων, προσθέστε το μικρότερο στον νέο πίνακα και μετακινήστε τον αντίστοιχο δείκτη.
4. Όταν ένας πίνακας τελειώσει, προσθέστε τα υπόλοιπα στοιχεία του άλλου πίνακα.

Παράδειγμα σε Kotlin (Android):

fun mergeSortedArrays(arr1: IntArray, arr2: IntArray): IntArray {
    val result = IntArray(arr1.size + arr2.size)
    var i = 0
    var j = 0
    var k = 0

    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++]
        } else {
            result[k++] = arr2[j++]
        }
    }

    while (i < arr1.size) {
        result[k++] = arr1[i++]
    }

    while (j < arr2.size) {
        result[k++] = arr2[j++]
    }

    return result
}

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