Ποιος αλγόριθμος ταξινόμησης χρησιμοποιείται στη λειτουργία sort;

Στη βιβλιοθήκη standard της C++, η λειτουργία std::sort υλοποιείται συνήθως χρησιμοποιώντας τον αλγόριθμο Introsort (Εισαγωγική Ταξινόμηση). Είναι ένας υβριδικός αλγόριθμος που συνδυάζει:

• Ταξινόμηση με Quicksort για τις περισσότερες περιπτώσεις
• Heapsort όταν το βάθος της αναδρομής γίνεται πολύ μεγάλο (για να αποφευχθεί η χειρότερη περίπτωση του Quicksort)
• Insertion Sort για μικρά υποπίνακες

Το Introsort εξασφαλίζει, κατά μέσο όρο, καλή απόδοση του Quicksort με την εγγύηση της χειρότερης περίπτωσης O(n log n), χάρη στη μετάβαση σε Heapsort.

Παράδειγμα χρήσης του std::sort:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {5, 3, 2, 4, 1};
    std::sort(v.begin(), v.end());
    for (int n : v) {
        std::cout << n << ' ';
    }
    return 0;
}

Έτσι, το std::sort είναι ένας υψηλής απόδοσης αλγόριθμος που βασίζεται στο Introsort.