red de ordenamiento

En ciencias de la computación, una red de ordenamiento (en inglés, sorting network) es un algoritmo que ordena un número fijo de valores mediante el uso de una secuencia fija de comparaciones. Esta puede ser imaginada como una red de hilos y módulos comparadores. Los valores (de cualquier tipo ordenable) fluyen a través de los hilos (no se debe confundir con hilo de ejecución). Cada comparador conecta dos hilos, compara los valores introducidos por los hilos, y los ordena obteniendo el menor como salida a un hilo, y el mayor a otro. Las redes de ordenamiento se diferencian del más general en el hecho de que no son capaces de manejar cantidades arbitrariamente grandes de entrada, y que su secuencia de comparaciones se conoce de antemano, independientemente del resultado de las comparaciones previas. Esta independencia de la secuencia de comparaciones es útil para la ejecución paralela y para su implementación en hardware. A pesar de la simplicidad de las redes de ordenamiento, su teoría es sorprendentemente profunda y compleja. Las redes de ordenamiento fueron primero estudiadas circa 1954 por Armstrong, Nelson y O'Connor,​ quienes subsecuentemente patentaron la idea.​ Las redes de ordenamiento pueden ser implementadas tanto en hardware como en software. Donald Knuth describe como los comparadores para los enteros binarios pueden ser implementados como sencillos dispositivos electrónicos de tres estados.​ , en 1968, sugirió usarlos para construir redes de interruptores para hardware de computadora, reemplazando a ambos: los buses de computadora y el más rápido pero más caro conmutador de barras cruzadas.​ Desde la década del 2000, las redes de ordenamiento (especialmente del ordenamiento bitónico) son usadas por la comunidad GPGPU para construir algoritmos de ordenamiento para correr en unidades de procesamiento gráfico.​