¿Hay un algoritmo de ordenamiento de enteros O (n)?

La última semana tropecé con este documento donde los autores mencionan en la segunda página:

Tenga en cuenta que esto produce un tiempo de ejecución lineal para los pesos enteros del borde.

Lo mismo en la tercera página:

Esto produce un tiempo de ejecución lineal para los pesos enteros del borde y O (m log n) para la clasificación basada en la comparación.

Y en la octava página:

En particular, el uso de la clasificación de enteros rápidos probablemente acelerará considerablemente el GPA.

¿Significa esto que hay un algoritmo de clasificación O (n) en circunstancias especiales para valores enteros? ¿O es esto una especialidad de la teoría de grafos?

PD:
Podría ser que la referencia [3] podría ser útil porque en la primera página dicen:

Se han logrado mejoras adicionales para [..] clases de gráficos como ponderaciones de borde entero [3], […]

pero no tuve acceso a ninguna de las revistas científicas.

Sí, la ordenación de radix y el conteo son O(N) . NO son géneros basados ​​en la comparación, que se ha demostrado tienen un límite inferior Ω(N log N) .

Para ser precisos, el orden de radix es O(kN) , donde k es el número de dígitos en los valores que se ordenarán. La clasificación de conteo es O(N + k) , donde k es el rango de los números que se ordenarán.

Existen aplicaciones específicas en las que k es lo suficientemente pequeño como para que el ordenamiento de radix y el tipo de recuento muestren un rendimiento de tiempo lineal en la práctica.

Los géneros de comparación deben ser al menos Ω (n log n) en promedio.

Sin embargo, el recuento de las escalas de ordenación y radix se realiza linealmente con el tamaño de entrada, ya que no son clases de comparación, sino que explotan la estructura fija de las entradas.

Clasificación de conteo: http://en.wikipedia.org/wiki/Counting_sort si tus enteros son bastante pequeños. Ordene la clasificación si tiene números más grandes (esto es básicamente una generalización de clasificación de conteo, o una optimización para números más grandes, si lo desea): http://en.wikipedia.org/wiki/Radix_sort

También hay clasificación de cubo: http://en.wikipedia.org/wiki/Bucket_sort

Si bien no es muy práctico (principalmente debido a la gran sobrecarga de memoria), pensé que mencionaría Abacus (Bead) Sort como otro algoritmo interesante de clasificación de tiempo lineal.

Estos algoritmos de clasificación basados ​​en hardware:

Algoritmo de clasificación sin comparación
Clasificación de números binarios en hardware: un algoritmo nuevo y su implementación

Algoritmo de clasificación de láser domino : un experimento de pensamiento basado en el recuento de ordenación con la intención de lograr una complejidad de tiempo de O(n) sobre el orden de conteo de O(n + k) .

Agregar un poco más de detalle: prácticamente el mejor algoritmo de clasificación hasta la fecha no es O (n), sino 0 (n \ sqrt {\ log \ log n}).

Puede consultar más detalles sobre este algo en el documento: http://dl.acm.org/citation.cfm?id=652131