Consegues nomear algoritmos cuja complexidade assintótica seja melhor do que a ordenação rápida?

A ordenação rápida funciona em média em O(n log n), o que é a melhor complexidade assintótica para algoritmos de comparação. No entanto, existem algoritmos com melhor complexidade assintótica em alguns casos:

• Ordenação por contagem (Counting Sort) — O(n + k), onde k é o intervalo de valores. Funciona mais rápido se k não for demasiado grande.
• Ordenação por radix (Radix Sort) — O(d * (n + k)), onde d é o número de dígitos, k é a base do sistema numérico. É eficiente para ordenar números ou strings.
• Ordenação por fusão (Merge Sort) — garantido O(n log n), estável e previsível.

Importante: algoritmos com melhor complexidade que O(n log n) não se baseiam na comparação de elementos, mas usam suposições adicionais sobre os dados (por exemplo, intervalo limitado de valores).