Puoi nominare algoritmi la cui complessità asintotica è migliore di quella di quicksort?

Il quicksort in media funziona in O(n log n), che rappresenta la migliore asintotica per gli algoritmi di confronto. Tuttavia, esistono algoritmi con una complessità asintotica migliore in alcuni casi:

• Sort counting (Counting Sort) — O(n + k), dove k è l'intervallo di valori. È più veloce se k non è troppo grande.
• Sort radix (Radix Sort) — O(d * (n + k)), dove d è il numero di cifre, k è la base del sistema numerico. È efficace per ordinare numeri o stringhe.
• Merge sort (Merge Sort) — garantito O(n log n), stabile e prevedibile.

Importante: gli algoritmi con una complessità migliore di O(n log n) non si basano sul confronto tra elementi, ma utilizzano supposizioni aggiuntive sui dati (ad esempio, intervallo limitato di valori).