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

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

Ιδέα:

• Υπάρχουν δύο ταξινομημένοι πίνακες ή λίστες.
• Χρησιμοποιούμε δύο δείκτες, έναν για κάθε πίνακα.
• Συγκρίνουμε τα τρέχοντα στοιχεία, το μικρότερο προστίθεται στο αποτέλεσμα και προχωράμε τον αντίστοιχο δείκτη.
• Επαναλαμβάνουμε μέχρι να διασχίσουμε και τους δύο πίνακες.

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

fun mergeSortedLists(a: List<Int>, b: List<Int>): List<Int> {
    val result = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < a.size && j < b.size) {
        if (a[i] <= b[j]) {
            result.add(a[i])
            i++
        } else {
            result.add(b[j])
            j++
        }
    }
    // Προσθέτουμε τα υπόλοιπα στοιχεία
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}