El método de ordenación por fusión de pares e impares de Batcher [1] es una construcción genérica ideada por Ken Batcher para ordenar redes de tamaño O( n (log n ) 2 ) y profundidad O((log n ) 2 ), donde n es el número de elementos que se van a ordenar. Aunque no es asintóticamente óptimo, Knuth concluyó en 1998, con respecto a la red AKS , que "el método de Batcher es mucho mejor, a menos que n exceda la capacidad total de memoria de todas las computadoras en la Tierra". [2]
Se popularizó con el segundo libro GPU Gems [3] , como una forma sencilla de realizar ordenaciones razonablemente eficientes en hardware de procesamiento de gráficos.
Existen varios esquemas recursivos e iterativos para calcular los índices de los elementos que se van a comparar y ordenar. Esta es una técnica iterativa para generar los índices para ordenar n elementos:
# nota: la secuencia de entrada está indexada de 0 a (n-1)para p = 1, 2, 4, 8, ... # siempre que p < n para k = p, p/2, p/4, p/8, ... # siempre que k >= 1 para j = mod(k,p) a (n-1-k) con un tamaño de paso de 2k para i = 0 a min(k-1, njk-1) con un tamaño de paso de 1 si piso((i+j) / (p*2)) == piso((i+j+k) / (p*2)) comparar y ordenar elementos (i+j) y (i+j+k)También es posible el cálculo no recursivo del índice del nodo asociado. [4]