Red de ordenamiento por pares

La red de ordenamiento por pares es una red de ordenamiento descubierta y publicada por Ian Parberry en 1992 en Parallel Processing Letters . ^[1] La red de ordenamiento por pares tiene el mismo tamaño (número de comparadores) y profundidad que la red de ordenamiento por fusión de pares e impares . En el momento de la publicación, la red era una de varias redes conocidas con una profundidad de . Requiere comparadores y tiene una profundidad de . ${\displaystyle O(\log ^{2}n)}$${\displaystyle n(\log n)(\log n-1)/4+n-1}$${\displaystyle (\log n)(\log n+1)/2}$

El procedimiento de clasificación implementado por la red es el siguiente (guiado por el principio cero-uno ):

1. Ordenar pares consecutivos de bits de la entrada (corresponde a la primera capa del diagrama)
2. Ordene todos los pares en orden lexicográfico ordenando recursivamente todos los bits impares y pares por separado (corresponde a las siguientes 14 capas del diagrama)
3. Ordenar los pares en orden no decreciente utilizando una red especializada (corresponde a las capas finales del diagrama)

La red de ordenación por pares es muy similar a la red de ordenación por combinación de pares e impares de Batcher, pero difiere en la estructura de las operaciones. Mientras que Batcher divide, ordena y fusiona repetidamente subsecuencias cada vez más largas, el método por pares realiza primero toda la subdivisión y luego toda la fusión al final en la secuencia inversa. En ciertas aplicaciones, como la codificación de restricciones de cardinalidad, la red de ordenación por pares es superior a la red de Batcher. ^[2]

• Redes de Ordenamiento – Archivo de página web del autor.