Estaba buscando un algoritmo de clasificación impar-par-fusión no recursivo y encontré 2 fuentes:

un libro deSedgewick R.estaSO pregunta

Ambos algoritmos son idénticos pero falsos. La red de clasificación resultante no es una red de clasificación de pares pares.

Aquí hay una imagen de la red resultante con 32 entradas. Una línea vertical entre 2 líneas horizontales significa comparar el valor a [x] con a [y], si es mayor, intercambie los valores en la matriz.

ordenamiento impar-par-combinado para 32 entradas http://flylib.com/books/3/55/1/html/2/images/11fig07.gif (se puede hacer clic)

Copié el código de Java a C y reemplacé elexch funcionar por unprintf para imprimir los candidatos de intercambio.

Cuando se dibuja un diagrama de los pares, se puede ver que se generan demasiados pares.

¿Alguien tiene una idea de cómo solucionar este algoritmo?

¿Por qué necesito una versión no recursiva?
Quiero transformar esta red de clasificación en hardware. Es fácil insertar etapas de canalización en algoritmos no recursivos.

También investigué la versión recursiva, pero es demasiado complejo transformar el algoritmo en hardware canalizado.

Mi código C:

#include <stdlib.h>
#include <stdio.h>

void sort(int l, int r)
{ int n = r-l+1;

  for (int p=1; p<n; p+=p)
    for (int k=p; k>0; k/=2)
      for (int j=k%p; j+k<n; j+=(k+k))
        for (int i=0; i<n-j-k; i++)
          if ((j+i)/(p+p) == (j+i+k)/(p+p))
              printf("%2i cmp %2i\n", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
  sort(0, COUNT);
}

El resultado:

0 -o--------o-------------------------o---------------o-------------------------
   |        |                         |               |
1 -o--------|-o------o----------------|-o-------------o-o-----------------------
            | |      |                | |               |
2 -o-o------o-|------o-o--------------|-|-o----o--------o-o---------------------
   | |        |        |              | | |    |          |
3 -o-o--------o--------o--------------|-|-|-o--|-o--------o-o-------o-----------
                                      | | | |  | |          |       |
4 -o-o-o----o---o----o-----o----------o-|-|-|--o-|-o--------o-o-----o-o---------
   | | |    |   |    |     |            | | |    | |          |       |
5 -o-o-o----|-o-|-o--o-o---o-o---o------o-|-|----o-|-o--------o-o-----o-o---o---
            | | | |    |     |   |        | |      | |          |       |   |
6 -o-o-o-o--o-|-o-|----o-o---o-o-o-o------o-|------o-|----------o-o-----o-o-o-o-
   | | | |    |   |      |     |   |        |        |            |       |   |
7 -o-o-o-o----o---o------o-----o---o--------o--------o------------o-------o---o-

Cuando sepa los pares de intercambio correctos y el algoritmo sea igual a la imagen, lo traduciré a VHDL para realizar pruebas en mi plataforma de hardware.

Otras implementaciones de red de clasificación de hardware de código abierto:

PoC.sort.sortnet.oddevensortPoC.sort.sortnet.bitonicsort

Apéndice:
La combinación de pares e impares (también conocida como la clasificación de Batcher) es como la clasificación bitónica (no confundir con la clasificación bitónica de Batcher). Pero en hardware, este algoritmo tiene una mejor complejidad de tamaño que el tipo bitónico, mientras que la latencia es la misma.

Estos algoritmos se pueden implementar con un buen uso de recursos en comparación con algoritmos de software rápidos como quicksort.

Wikipedia:combinación impar-par

Nota:
Debido a que las redes de clasificación son estáticas e independientes de los valores de entrada, no es necesario comparar e intercambiar para generar la red. Esa es una razón por la que se puede transformar en hardware. Mi código genera los índices para las operaciones de comparación. En hardware, estas conexiones verticales serán reemplazadas por circuitos de comparación e intercambio. Por lo tanto, los datos no clasificados viajarán a través de la red y en el lado de salida se ordenarán.