La clasificación mediante comparaciones de 2 elementos tiene una complejidad asintótica en el peor de los casos de (alcanzado por mergesort, heapsort, inserción binaria, ford-johnson al menos), lo cual es óptimo.
Si ordenamos usando comparaciones que ordenan k elementos como bloques de construcción, el límite inferior teórico de información es . Podemos alcanzar fácilmente n log k ( n ) con inserción k-aria.
Pregunta: ¿Dónde está la complejidad óptimo entre y n log k ! ( n ) ?
Los árbitros apropiados también serían apreciados.
Editar: porque no estaba claro:
Estoy interesado en la complejidad de , con k = O ( 1 ) . Tiene el comportamiento asintótico de α n log 2 ( n ) con α ∈ [ 1, y me gustaría tener más precisión sobreα.