Tipo de casillero

La clasificación por casilleros es un algoritmo de clasificación adecuado para clasificar listas de elementos donde el número n de elementos y la longitud N de los rango de posibles valores clave son aproximadamente los mismos. Requiere tiempo O(n + N). Es similar a la ordenación por conteo, pero se diferencia en que "mueve elementos dos veces: una vez a la matriz de cubos y otra vez al destino final [mientras que] la ordenación por conteo crea una matriz auxiliar y luego usa la matriz para calcular cada elemento's destino final y mueva el elemento allí."

El algoritmo del casillero funciona de la siguiente manera:

1. Dada una serie de valores que deben ser ordenados, establecer una matriz auxiliar de "pigeonholes" inicialmente vacíos, un agujero de paloma para cada llave en el rango de las teclas en el array original.
2. Pasando por encima de la matriz original, poner cada valor en el agujero de paloma correspondiente a su clave, de tal manera que cada agujero de paloma finalmente contiene una lista de todos los valores con esa clave.
3. Itear sobre la matriz de palomas en orden creciente de llaves, y para cada agujero de paloma, poner sus elementos en la matriz original en orden creciente.