Describimos un algoritmo que calcula un código óptimo libre de prefijos para pesos positivos no ordenados en tiempo dentro de , donde la alternancia aproxima la cantidad mínima de ordenación requerida por la computación. Esta complejidad asintótica está dentro de un factor constante de lo óptimo en el modelo computacional del árbol de decisiones algebraicas, en el peor de los casos sobre todas las instancias de tamaño y alternancia . Tales resultados refinan el estado del arte de la complejidad en el peor de los casos sobre instancias de tamaño en el mismo modelo computacional, un hito en compresión y codificación desde 1952. Además de la nueva técnica de análisis, esta mejora se obtiene combinando un nuevo algoritmo, inspirado en el algoritmo de van Leeuwen para calcular códigos óptimos libres de prefijo a partir de pesos ordenados (conocido desde 1976), con una extensión relativamente menor de la estructura de datos diferida de Karp et al. para ordenar parcialmente un multiconjunto de acuerdo con las consultas realizadas en él (conocido desde 1988). Los resultados experimentales preliminares sobre compresión de texto por palabras muestran ser polinomialmente más pequeños que , lo que sugiere mejoras en el tiempo de ejecución para tales aplicaciones en un factor multiplicativo constante como máximo.