En informática , la clasificación de números enteros es el problema algorítmico de clasificar una colección de valores de datos mediante claves de números enteros . Los algoritmos diseñados para la clasificación de enteros también se pueden aplicar a menudo a problemas de clasificación en los que las claves son números de punto flotante , números racionales o cadenas de texto. [1] La capacidad de realizar aritmética de números enteros en las claves permite que los algoritmos de clasificación de números enteros sean más rápidos que los algoritmos de clasificación de comparación en muchos casos, dependiendo de los detalles de qué operaciones están permitidas en el modelo de computación y del tamaño de los números enteros que se van a clasificar. .
Los algoritmos de clasificación de enteros, que incluyen clasificación por casillero , clasificación por recuento y clasificación por base, se utilizan ampliamente y son prácticos. No se cree que otros algoritmos de clasificación de enteros con límites de tiempo más pequeños en el peor de los casos sean prácticos para arquitecturas de computadora con 64 bits o menos por palabra. Se conocen muchos de estos algoritmos, y el rendimiento depende de una combinación del número de elementos a clasificar, el número de bits por clave y el número de bits por palabra del ordenador que realiza el algoritmo de clasificación.
Consideraciones Generales
Modelos de computación
Los límites de tiempo para los algoritmos de ordenación de enteros generalmente dependen de tres parámetros: el número n de valores de datos que se van a ordenar, la magnitud K de la clave más grande posible que se va a ordenar y el número w de bits que se pueden representar en una sola palabra de máquina de el ordenador en el que se va a realizar el algoritmo. Normalmente, se supone que w ≥ log 2 (max ( n , K )) ; es decir, que las palabras de máquina son lo suficientemente grandes como para representar un índice en la secuencia de datos de entrada, y también lo suficientemente grandes como para representar una sola clave. [2]
Los algoritmos de clasificación de enteros generalmente están diseñados para funcionar en modelos informáticos de máquina de puntero o de máquina de acceso aleatorio . La principal diferencia entre estos dos modelos está en cómo se puede abordar la memoria. La máquina de acceso aleatorio permite que cualquier valor almacenado en un registro sea utilizado como dirección de operaciones de lectura y escritura de memoria, con costo unitario por operación. Esta capacidad permite implementar rápidamente ciertas operaciones complejas en datos mediante búsquedas de tablas. Por el contrario, en el modelo de máquina de punteros, las operaciones de lectura y escritura utilizan direcciones almacenadas en punteros y no se permite realizar operaciones aritméticas en estos punteros. En ambos modelos, se pueden agregar valores de datos, y las operaciones booleanas bit a bit y las operaciones de desplazamiento binario también se pueden realizar típicamente en ellos, en unidad de tiempo por operación. Sin embargo, los diferentes algoritmos de ordenación de enteros hacen diferentes suposiciones sobre si la multiplicación de enteros también está permitida como una operación de unidad de tiempo. [3] También se han considerado otros modelos de cálculo más especializados, como la máquina de acceso aleatorio en paralelo . [4]
Andersson, Miltersen y Thorup (1999) demostraron que en algunos casos las multiplicaciones o búsquedas de tablas requeridas por algunos algoritmos de ordenación de enteros podrían reemplazarse por operaciones personalizadas que se implementarían más fácilmente en hardware pero que normalmente no están disponibles en computadoras de uso general. Thorup (2003) mejoró esto mostrando cómo reemplazar estas operaciones especiales por las instrucciones de manipulación de campo de bits ya disponibles en los procesadores Pentium .
En los modelos informáticos de memoria externa , ningún algoritmo de clasificación de enteros conocido es más rápido que la clasificación por comparación. Los investigadores han demostrado que, en estos modelos, las clases restringidas de algoritmos que están limitados en la forma en que manipulan sus claves no pueden ser más rápidas que la clasificación por comparación, [5] y que un algoritmo de clasificación de enteros que sea más rápido que la clasificación por comparación implicaría la falsedad de un conjetura estándar en codificación de redes . [6]
Ordenación frente a colas de prioridad entera
Una cola de prioridad es una estructura de datos para mantener una colección de elementos con prioridades numéricas, con operaciones para encontrar y eliminar el elemento con el valor de prioridad mínimo. Las colas de prioridad basadas en comparación, como el montón binario, toman un tiempo logarítmico por actualización, pero otras estructuras como el árbol de van Emde Boas o la cola de cubos pueden ser más rápidas para las entradas cuyas prioridades son números enteros pequeños. Estas estructuras de datos se pueden utilizar en el algoritmo de clasificación de selección , que clasifica una colección de elementos encontrando y eliminando repetidamente el elemento más pequeño de la colección y devolviendo los elementos en el orden en que se encontraron. Se puede usar una cola de prioridad para mantener la colección de elementos en este algoritmo, y el tiempo para este algoritmo en una colección de n elementos puede estar limitado por el tiempo para inicializar la cola de prioridad y luego realizar n operaciones de búsqueda y eliminación. Por ejemplo, el uso de un montón binario como una cola de prioridad en el ordenamiento de selección conduce al algoritmo de ordenamiento del montón , un algoritmo de ordenamiento por comparación que toma O ( n log n ) tiempo. En cambio, el uso de la ordenación por selección con una cola de cubos proporciona una forma de ordenación en casillero , y el uso de árboles de van Emde Boas u otras colas de prioridad de enteros conduce a otros algoritmos rápidos de ordenación de enteros. [7]
En lugar de usar una cola de prioridad entera en un algoritmo de clasificación, es posible ir en la otra dirección y usar algoritmos de clasificación entera como subrutinas dentro de una estructura de datos de cola de prioridad entera. Thorup (2007) usó esta idea para mostrar que, si es posible realizar una clasificación de enteros en el tiempo T ( n ) por clave, entonces el mismo límite de tiempo se aplica al tiempo por operación de inserción o eliminación en una estructura de datos de cola de prioridad. La reducción de Thorup es complicada y asume la disponibilidad de operaciones de multiplicación rápidas o búsquedas en tablas, pero también proporciona una cola de prioridad alternativa usando solo operaciones de suma y booleanas con tiempo T ( n ) + T (log n ) + T (log log n ) + ... por operación, como máximo multiplicando el tiempo por un logaritmo iterado . [7]
Usabilidad
Los algoritmos clásicos de clasificación de enteros de clasificación en casillero , clasificación de conteo y clasificación de base son ampliamente utilizados y prácticos. [8] Gran parte de la investigación posterior sobre algoritmos de ordenación de enteros se ha centrado menos en la practicidad y más en las mejoras teóricas en el análisis del peor de los casos , y los algoritmos que provienen de esta línea de investigación no se cree que sean prácticos para las computadoras actuales de 64 bits. arquitecturas, aunque los experimentos han demostrado que algunos de estos métodos pueden ser una mejora en la clasificación por radix para datos con 128 o más bits por clave. [9] Además, para grandes conjuntos de datos, los patrones de acceso a la memoria casi aleatorios de muchos algoritmos de clasificación de enteros pueden obstaculizarlos en comparación con los algoritmos de clasificación de comparación que se han diseñado teniendo en cuenta la jerarquía de la memoria . [10]
La clasificación de enteros proporciona uno de los seis puntos de referencia en el conjunto de puntos de referencia de Matemáticas discretas de los sistemas informáticos de alta productividad de DARPA , [11] y uno de los once puntos de referencia en el conjunto de puntos de referencia NAS Parallel Benchmarks .
Algoritmos prácticos
La clasificación por casillero o la clasificación por recuento pueden clasificar n elementos de datos que tienen claves en el rango de 0 a K - 1 en el tiempo O ( n + K ) . En la clasificación de casilleros (a menudo denominada clasificación de cubos), los punteros a los elementos de datos se distribuyen en una tabla de cubos, representados como tipos de datos de recopilación , como listas vinculadas , utilizando las claves como índices en la tabla. Luego, todos los depósitos se concatenan para formar la lista de salida. [12] La clasificación por conteo utiliza una tabla de contadores en lugar de una tabla de cubos, para determinar el número de elementos con cada clave. Luego, se usa un cálculo de suma de prefijo para determinar el rango de posiciones en la salida ordenada en la que se deben colocar los valores con cada clave. Finalmente, en una segunda pasada sobre la entrada, cada elemento se mueve a la posición de su clave en la matriz de salida. [13] Ambos algoritmos involucran solo bucles simples sobre los datos de entrada (tomando el tiempo O ( n ) ) y sobre el conjunto de claves posibles (tomando el tiempo O ( K ) ), dando su límite de tiempo total O ( n + K ) .
La clasificación por radix es un algoritmo de clasificación que funciona para claves más grandes que la clasificación por casillero o la clasificación por recuento al realizar varias pasadas sobre los datos. Cada pasada clasifica la entrada usando solo una parte de las claves, usando un algoritmo de clasificación diferente (como clasificación por casillero o clasificación por conteo) que es adecuado solo para llaves pequeñas. Para dividir las claves en partes, el algoritmo de ordenación por base calcula la notación posicional para cada tecla, de acuerdo con alguna base elegida ; luego, la parte de la clave usada para el i- ésimo paso del algoritmo es el i- ésimo dígito en la notación posicional para la clave completa, comenzando desde el dígito menos significativo y progresando hasta el más significativo. Para que este algoritmo funcione correctamente, el algoritmo de clasificación utilizado en cada pasada sobre los datos debe ser estable : los elementos con dígitos iguales no deben cambiar de posición entre sí. Para mayor eficiencia, la base debe elegirse para que esté cerca del número de elementos de datos, n . Además, el uso de una potencia de dos cerca de n como base permite que las teclas de cada pasada se calculen rápidamente utilizando solo operaciones binarias rápidas de cambio y máscara. Con estas opciones, y con la clasificación en casillero o la clasificación por recuento como algoritmo base, el algoritmo de clasificación por base puede clasificar n elementos de datos que tienen claves en el rango de 0 a K - 1 en el tiempo O ( n log n K ) . [14]
Algoritmos teóricos
Se han desarrollado muchos algoritmos de ordenación de enteros cuyo análisis teórico muestra que se comportan mejor que la ordenación por comparación, la ordenación por casilleros o la ordenación por base para combinaciones suficientemente grandes de los parámetros que definen el número de elementos a ordenar, el rango de claves y el tamaño de la palabra de la máquina. Qué algoritmo tiene el mejor rendimiento depende de los valores de estos parámetros. Sin embargo, a pesar de sus ventajas teóricas, estos algoritmos no son una mejora para los rangos típicos de estos parámetros que surgen en problemas prácticos de clasificación. [9]
Algoritmos para teclas pequeñas
Se puede usar un árbol de Van Emde Boas como cola de prioridad para ordenar un conjunto de n claves, cada una en el rango de 0 a K - 1 , en el tiempo O ( n log log K ) . Esta es una mejora teórica sobre la clasificación por radix cuando K es suficientemente grande. Sin embargo, para usar un árbol de Van Emde Boas, se necesita una memoria directamente direccionable de K palabras, o se necesita simularla usando una tabla hash , reduciendo el espacio a lineal pero haciendo que el algoritmo sea aleatorio. Otra cola de prioridad con un rendimiento similar (incluida la necesidad de aleatorización en forma de tablas hash) es el ensayo Y-fast de Willard (1983) .
Kirkpatrick & Reisch (1984) desarrollaron una técnica más sofisticada con un sabor similar y con mejor rendimiento teórico . Observaron que cada pasada de ordenación de radix puede interpretarse como una técnica de reducción de rango que, en tiempo lineal, reduce el tamaño máximo de clave en un factor de n ; en cambio, su técnica reduce el tamaño de la clave a la raíz cuadrada de su valor anterior (reduciendo a la mitad el número de bits necesarios para representar una clave), nuevamente en tiempo lineal. Al igual que en Radix sort, interpretan las teclas como base- de dos dígitos b números para una base b que es aproximadamente √ K . Luego, agrupan los elementos que se clasificarán en cubos de acuerdo con sus dígitos altos, en tiempo lineal, utilizando una memoria de dirección directa grande pero no inicializada o una tabla hash. Cada cubo tiene un representante, el artículo del cubo con la clave más grande; luego clasifican la lista de elementos utilizando como claves los dígitos altos para los representantes y los dígitos bajos para los no representantes. Al volver a agrupar los elementos de esta lista en depósitos, cada depósito se puede colocar en orden clasificado, y al extraer los representantes de la lista clasificada, los depósitos se pueden concatenar juntos en orden clasificado. Así, en tiempo lineal, el problema de clasificación se reduce a otro problema de clasificación recursiva en el que las claves son mucho más pequeñas, la raíz cuadrada de su magnitud anterior. La repetición de esta reducción de rango hasta que las claves sean lo suficientemente pequeñas para clasificar en cubos conduce a un algoritmo con tiempo de ejecución O ( n log log n K ) .
Un complicado algoritmo aleatorio de Han y Thorup (2002) en el modelo de cálculo RAM de palabras permite que estos límites de tiempo se reduzcan aún más, a O ( n √ log log K ) .
Algoritmos para palabras grandes
Se dice que un algoritmo de clasificación de enteros no es conservador si requiere un tamaño de palabra w que es significativamente mayor que log max ( n , K ) . [15] Como ejemplo extremo, si w ≥ K , y todas las claves son distintas, entonces el conjunto de claves se puede ordenar en tiempo lineal representándolo como un vector de bits , con un 1 bit en la posición i cuando i es uno de los teclas de entrada, y luego eliminando repetidamente el bit menos significativo. [dieciséis]
El no conservadora lleno algoritmo de ordenación de Albers y Hagerup (1997) utiliza una subrutina, basado en Ken Dosificadores 's red de ordenación bitónica , por la fusión de dos ordenados secuencias de teclas que son cada uno lo suficientemente corto para ser embalado en una sola palabra máquina. La entrada al algoritmo de clasificación empaquetada, una secuencia de elementos almacenados uno por palabra, se transforma en una forma empaquetada, una secuencia de palabras que contiene varios elementos en orden ordenado, utilizando esta subrutina repetidamente para duplicar el número de elementos empaquetados en cada uno. palabra. Una vez que la secuencia está en forma empaquetada, Albers y Hagerup usan una forma de clasificación de combinación para clasificarla; cuando se fusionan dos secuencias para formar una única secuencia más larga, se puede utilizar la misma subrutina de clasificación bitónica para extraer repetidamente palabras empaquetadas que constan de los elementos restantes más pequeños de las dos secuencias. Este algoritmo obtiene una aceleración suficiente de su representación empaquetada para ordenar su entrada en tiempo lineal siempre que sea posible que una sola palabra contenga claves Ω (log n log log n ) ; es decir, cuando log K log n log log n ≤ cw para alguna constante c > 0 .
Algoritmos para pocos elementos
La clasificación por casillero, la clasificación por recuento, la clasificación por radix y la clasificación por árboles de Van Emde Boas funcionan mejor cuando el tamaño de la clave es pequeño; para claves suficientemente grandes, se vuelven más lentos que los algoritmos de clasificación por comparación. Sin embargo, cuando el tamaño de la clave o el tamaño de la palabra es muy grande en relación con el número de elementos (o de manera equivalente cuando el número de elementos es pequeño), puede volver a ser posible ordenar rápidamente, utilizando diferentes algoritmos que aprovechan el paralelismo inherente. en la capacidad de realizar operaciones aritméticas en palabras grandes.
Ajtai, Fredman y Komlós (1984) proporcionaron un resultado temprano en esta dirección utilizando el modelo de computación de sonda celular (un modelo artificial en el que la complejidad de un algoritmo se mide solo por el número de accesos a la memoria que realiza). Basándose en su trabajo, Fredman y Willard (1994) describieron dos estructuras de datos, Q-heap y atomic heap, que se pueden implementar en una máquina de acceso aleatorio. El Q-heap es una versión en paralelo de bits de un trie binario , y permite que tanto las operaciones de cola de prioridad como las consultas sucesoras y predecesoras se realicen en tiempo constante para conjuntos de O ((log N ) 1/4 ) elementos, donde N ≤ 2 w es el tamaño de las tablas precalculadas necesarias para implementar la estructura de datos. El montón atómico es un árbol B en el que cada nodo del árbol se representa como un montón Q; permite operaciones de cola de prioridad de tiempo constante (y por lo tanto clasificación) para conjuntos de elementos (log N ) O (1) .
Andersson y col. (1998) proporcionan un algoritmo aleatorio llamado clasificación de firmas que permite la clasificación lineal en el tiempo de conjuntos de hasta 2 O ((log w ) 1/2 - ε ) elementos a la vez, para cualquier constante ε> 0 . Al igual que en el algoritmo de Kirkpatrick y Reisch, realizan una reducción de rango utilizando una representación de las claves como números en la base b para una elección cuidadosa de b . Su algoritmo de reducción de rango reemplaza cada dígito por una firma, que es un valor hash con O (log n ) bits, de modo que los diferentes valores de los dígitos tienen diferentes firmas. Si n es lo suficientemente pequeño, los números formados por este proceso de reemplazo serán significativamente más pequeños que las claves originales, lo que permitirá que el algoritmo de clasificación empaquetada no conservadora de Albers & Hagerup (1997) clasifique los números reemplazados en tiempo lineal. A partir de la lista ordenada de números reemplazados, es posible formar un trie comprimido de las claves en tiempo lineal, y los hijos de cada nodo en el trie pueden ordenarse de forma recursiva usando solo claves de tamaño b , después de lo cual un recorrido de árbol produce el orden ordenado de los elementos.
Algoritmos trans-dicotómicos
Fredman y Willard (1993) introdujeron el modelo de análisis transdicotómico para algoritmos de ordenación de números enteros, en el que no se asume nada sobre el rango de las claves de números enteros y se debe limitar el rendimiento del algoritmo por una función del número de valores de datos únicamente. Alternativamente, en este modelo, se supone que el tiempo de ejecución de un algoritmo en un conjunto de n elementos es el tiempo de ejecución del peor caso para cualquier combinación posible de valores de K y w . El primer algoritmo de este tipo fue el algoritmo de clasificación del árbol de fusión de Fredman y Willard , que se ejecuta en el tiempo O ( n log n / log log n ) ; esto es una mejora con respecto a la clasificación por comparación para cualquier elección de K y w . Una versión alternativa de su algoritmo que incluye el uso de números aleatorios y operaciones de división de enteros mejora esto a O ( n √ log n ) .
Desde su trabajo, se han desarrollado incluso mejores algoritmos. Por ejemplo, al aplicar repetidamente la técnica de reducción de rango de Kirkpatrick-Reisch hasta que las claves sean lo suficientemente pequeñas para aplicar el algoritmo de clasificación empaquetada de Albers-Hagerup, es posible clasificar en el tiempo O ( n log log n ) ; sin embargo, la parte de reducción de rango de este algoritmo requiere una gran memoria (proporcional a √ K ) o una aleatorización en forma de tablas hash. [17]
Han y Thorup (2002) mostraron cómo ordenar en tiempo aleatorio O ( n √ log log n ) . Su técnica implica el uso de ideas relacionadas con la clasificación de firmas para dividir los datos en muchas sublistas pequeñas, de un tamaño lo suficientemente pequeño como para que la clasificación de firmas pueda clasificar cada una de ellas de manera eficiente. También es posible utilizar ideas similares para ordenar números enteros de forma determinista en el tiempo O ( n log log n ) y el espacio lineal. [18] Usando solo operaciones aritméticas simples (sin multiplicaciones ni búsquedas en tablas) es posible ordenar en el tiempo esperado aleatorio O ( n log log n ) [19] o de manera determinista en el tiempo O ( n (log log n ) 1 + ε ) para cualquier constante ε> 0 . [1]
Referencias
- Notas al pie
- ↑ a b Han y Thorup (2002) .
- ^ Fredman y Willard (1993) .
- ^ La cuestión de si deberían permitirse las operaciones de multiplicación de enteros o de búsqueda de tablas se remonta a Fredman y Willard (1993) ; véase también Andersson, Miltersen y Thorup (1999) .
- ^ Reif (1985) ; comentario en Cole y Vishkin (1986) ; Hagerup (1987) ; Bhatt y col. (1991) ; Albers y Hagerup (1997) .
- ^ Aggarwal y Vitter (1988) .
- ^ Farhadi y col. (2020) .
- ↑ a b Chowdhury (2008) .
- ^ McIlroy, Bostic y McIlroy (1993) ; Andersson y Nilsson (1998) .
- ↑ a b Rahman y Raman (1998) .
- ^ Pedersen (1999) .
- ^ DARPA HPCS Discrete Mathematics Benchmarks , Duncan A. Buell, Universidad de Carolina del Sur, consultado el 20 de abril de 2011 .
- ^ Goodrich y Tamassia (2002) . Aunque Cormen et al. (2001) también describen una versión de este algoritmo de clasificación, la versión que describen está adaptada a entradas donde las claves son números reales con una distribución conocida, en lugar de una clasificación de enteros.
- ^ Cormen y col. (2001) , 8.2 Counting Sort, págs. 168-169.
- ^ Comrie (1929-1930) ; Cormen y col. (2001) , 8.3 Radix Sort, págs. 170-173.
- ^ Kirkpatrick y Reisch (1984) ; Albers y Hagerup (1997) .
- ^ Kirkpatrick y Reisch (1984) .
- ^ Andersson y col. (1998) .
- ^ Han (2004) .
- ^ Thorup (2002)
- Fuentes secundarias
- Chowdhury, Rezaul A. (2008), "Equivalencia entre colas de prioridad y clasificación" , en Kao, Ming-Yang (ed.), Encyclopedia of Algorithms , Springer, págs. 278-281, ISBN 9780387307701.
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Introducción a los algoritmos (2a ed.), MIT Press y McGraw-Hill , ISBN 0-262-03293-7.
- Goodrich, Michael T .; Tamassia, Roberto (2002), "4.5 Bucket-Sort y Radix-Sort", Diseño de algoritmos: Fundamentos, análisis y ejemplos de Internet , John Wiley & Sons, págs. 241–243.
- Fuentes primarias
- Aggarwal, Alok; Vitter, Jeffrey S. (septiembre de 1988), "La complejidad de entrada / salida de la clasificación y problemas relacionados", Comunicaciones del ACM , 31 (9): 1116–1127, doi : 10.1145 / 48529.48535
- Ajtai, M .; Fredman, M .; Komlós, J. (1984), "Funciones hash para colas de prioridad", Información y control , 63 (3): 217–225, doi : 10.1016 / S0019-9958 (84) 80015-7 , MR 0837087.
- Albers, Susanne ; Hagerup, Torben (1997), "Mejor ordenación de enteros paralelos sin escritura concurrente", Información y Computación , 136 (1): 25–51, CiteSeerX 10.1.1.53.498 , doi : 10.1006 / inco.1997.2632 , MR 1457693.
- Andersson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (1998), "Sorting in linear time?", Journal of Computer and System Sciences , 57 (1): 74–93, doi : 10.1006 / jcss.1998.1580 , MR 1649809.
- Andersson, Arne; Nilsson, Stefan (1998), "Implementing radixsort", ACM Journal of Experimental Algorithmics , 3 : 7 – es, CiteSeerX 10.1.1.54.4536 , doi : 10.1145 / 297096.297136 , MR 1717389.
- Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), "Los árboles de fusión se pueden implementar solo con instrucciones AC 0 ", Theoretical Computer Science , 215 (1–2): 337–344, CiteSeerX 10.1.1.32.9401 , doi : 10.1016 / S0304-3975 ( 98) 00172-8 , MR 1678804.
- Bhatt, PCP; Diks, K .; Hagerup, T .; Prasad, VC; Radzik, T .; Saxena, S. (1991), "Mejor ordenación determinista de enteros paralelos", Información y Computación , 94 (1): 29–47, doi : 10.1016 / 0890-5401 (91) 90031-V , MR 1123154.
- Cole, R .; Vishkin, U. (1986), "Lanzamiento de moneda determinista con aplicaciones para la clasificación de lista paralela óptima", Información y control , 70 (1): 32-53, doi : 10.1016 / S0019-9958 (86) 80023-7.
- Comrie, LJ (1929-1930), "Las máquinas de tabulación de Hollerith and Powers", Trans. Office Mach. Asociación de usuarios, LTD. : 25–37CS1 maint: ref duplica el valor predeterminado ( enlace ). Citado por Thorup (2007) como una de las primeras fuentes para la ordenación por radix .
- Farhadi, Alireza; Hajiaghayi, Mohammad Taghi ; Larsen, Kasper Green; Shi, Elaine (septiembre de 2020), "Límites inferiores para la clasificación de enteros de memoria externa mediante codificación de red", Comunicaciones del ACM , 63 (10): 97–105, arXiv : 1811.01313 , doi : 10.1145 / 3416268.
- Fredman, Michael L .; Willard, Dan E. (1993), "Superando el límite de la teoría de la información con árboles de fusión", Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016 / 0022-0000 (93) 90040-4 , MR 1248864.
- Fredman, Michael L .; Willard, Dan E. (1994), "Algoritmos trans-dicotómicos para árboles de expansión mínimos y rutas más cortas", Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016 / S0022-0000 (05) 80064 -9 , MR 1279413.
- Hagerup, Torben (1987), "Hacia una clasificación óptima de cubetas paralelas", Information and Computation , 75 (1): 39–51, doi : 10.1016 / 0890-5401 (87) 90062-9 , MR 0910976.
- Han, Yijie (2004), "Clasificación determinista en O ( n log log n ) tiempo y espacio lineal", Journal of Algorithms , 50 (1): 96-105, doi : 10.1016 / j.jalgor.2003.09.001 , MR 2028585.
- Han, Yijie; Thorup, M. (2002), "Clasificación de enteros en O ( n √ log log n ) tiempo esperado y espacio lineal", Actas del 43 ° Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS 2002) , IEEE Computer Society, págs. 135 –144, doi : 10.1109 / SFCS.2002.1181890.
- Kirkpatrick, David ; Reisch, Stefan (1984), "Límites superiores para clasificar enteros en máquinas de acceso aleatorio", Ciencias de la computación teóricas , 28 (3): 263-276, doi : 10.1016 / 0304-3975 (83) 90023-3 , MR 0742289.
- McIlroy, Peter M .; Bostic, Keith; McIlroy, M. Douglas (1993), "Engineering Radix Sort" (PDF) , Computing Systems , 6 (1): 5–27.
- Pedersen, Morten Nicolaj (1999), Un estudio de la importancia práctica de los algoritmos RAM de palabras para la ordenación interna de números enteros , Tesis de maestría, Departamento de Ciencias de la Computación, Universidad de Copenhague, Dinamarca, archivado desde el original el 16 de marzo de 2012 , recuperado en 2011 -04-21.
- Rahman, Naila; Raman, Rajeev (1998), "Un estudio experimental del paralelismo a nivel de palabra en algunos algoritmos de ordenación", Ingeniería de algoritmos, 2do Taller Internacional, WAE '92, Saarbrücken, Alemania, 20-22 de agosto de 1998, Actas (PDF) , Max Instituto Planck de Ciencias de la Computación , págs. 193–203.
- Reif, John H. (1985), "Un algoritmo paralelo óptimo para la ordenación de enteros", Actas del 26º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS 1985) , IEEE Computer Society, págs. 496–504, doi : 10.1109 / SFCS .1985.9.
- Thorup, Mikkel (2002), "Clasificación aleatoria en el tiempo O ( n log log n ) y el espacio lineal mediante operaciones booleanas de suma, desplazamiento y bits", Journal of Algorithms , 42 (2): 205-230, CiteSeerX 10.1 .1.55.4443 , doi : 10.1006 / jagm.2002.1211 , MR 1895974.
- Thorup, Mikkel (2003), "Sobre las implementaciones de AC 0 de árboles de fusión y pilas atómicas", Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos (Baltimore, MD, 2003) , Nueva York: ACM, págs. 699–707 , MR 1974982.
- Thorup, Mikkel (2007), "Equivalencia entre colas de prioridad y clasificación", Revista de la ACM , 54 (6): Art. 28, doi : 10.1145 / 1,314,690.1314692 , MR 2374029.
- Willard, Dan E. (1983), "Las consultas de rango logarítmico del peor caso son posibles en el espacio Θ ( N ) ", Information Processing Letters , 17 (2): 81–84, doi : 10.1016 / 0020-0190 (83 ) 90075-3 , MR 0731126.