Bitonic Sort

Bitonic Sort con la propiedad de que la secuencia de comparaciones es independiente de datos hace que sea uno de los paralelos más rápida y adecuada algoritmos de ordenación. Para ordenar una secuencia arbitraria bitónica tiene dos pasos. En el primer paso se hace que la secuencia arbitraria entre en la secuencia bitónica. Una secuencia bitónica es una secuencia que o bien aumenta o disminuye monotónicamente, alcanza un único máximo o mínimo, y a continuación, después de que el valor máximo o mínimo de nuevo monotónicamente aumenta o disminuye. Por ejemplo, las dos secuencias de 3 5 8 9 7 4 2 1 y 5 8 9 7 4 2 1 3 son bitónica. El primero aumenta de 3 a 9, luego disminuye. El segundo uno se puede convertir en el primero desplazando cíclicamente. En la segunda etapa de la secuencia de bitónica se ordena de tal manera que, permite que tenemos una secuencia bitónica N con longitud N = 2^k, lo que requeriría k pasos para ordenar una longitud total de n elementos. En la primera etapa de N (0) se compara con n (n / 2), N (1) con N (n / 2 +1) hasta N (N/2-1) con N (n-1) y los elementos se intercambian de acuerdo ya sea ascendente o descendente. Este proceso daría lugar a dos subsecuencias a partir de N (0) a N (N / 2) y de N (N / 2+1) a N (N-1). Luego, en el segundo paso el mismo procedimiento aplicaría a cada subsecuencia y cada subsecuencia produciría otra subsecuencia y después de la etapa de orden k se obtienen las 2^k subsecuencias de longitud 1 por lo que todos los elementos de la secuencia bitónica están siendo ordenados.

...