Código C

#include <pvm3.h>
#include <stdio.h>
#include <math.h>

#define NPROC 16 //utilizou-se 16 processadores - 2 hipercubos
#define d 2 // variavel global que representa a distancia entre os elementos comparados
#define m 4    // numero de iteracoes para 16 processadores

// definição da função max() que retorna o maior valor entre 2 valores
int max(int x, int y) { 
    int maximo = x;
	if (y  >  maximo)
	   maximo = y;
	   return maximo;
}  

// definição das função min() que retorna o menor valor entre 2 valores
int min(int x, int y) { 
    int minimo = x;
	if (y < minimo)
	   minimo =  y;
	   return minimo;
}  
dowork( int me, int *tids, int nproc ) {
int t;    // variavel temporaria para salvar o conteudo do processador adjacente
	for ( int k = 0; k <= pow( 2, m ) - 1; k++ ) {
		if ( ( k % ( 2 * d ) ) < d ) {
			t = &tids[ k + d ]; // obtem o valor que está no processador adjacente
			if ( k % pow( 2, i + 2 ) < pow( 2, i + 1 ) ) {
				&tids[ k + d ] = max( t, &tids[ k ] ); // ordenação ascendente
				&tids[ k ] = min( t, &tids[ k ] );
			} // endif
			else {
				&tids[k + d] = min( t, &tids[ k ] ); // ordenação descendente
				&tids[ k ] = max( t, &tids[ k ] );
			} // endelse potencia de 2 elevado a i + 2 
		}  // endif do 2*d
	} // endfor do k
}  // end dowork

int main(int argc, char** argv[]) {
     int	a,                       		// conteudo do processador corrente
	t,                       		// conteudo recuperado do processador adjacente
	mytid,	// identificacao do meu processo
	tids[ NPROC ],	// vetor de processos
	me,	// processador master
	ind;	// indice do vetor de processos
	mytid = pvm_mytid();
	tids[ 0 ] = pvm_parent();
	if( tids[ 0 ] < 0 ) {
		tids[ 0 ] = mytid;
		me = 0;
		pvm_spawn ("bms", (char **)0, 0, "", NPROC-1, &tids[1]); //bms-aplicacao
		pvm_initsend( PvmDataDefault );
		pvm_pkint(tids, NPROC, 1);
		pvm_mcast(&tids[1], NPROC-1, 0);
	}
	else {
		pvm_recv(tids[0], 0);
		pvm_upkint(tids, NPROC, 1);
		for( int h = 1; h < NPROC; h++ )
			if (mytid == tids[h] ) { me = h; break;  }
	}
	dowork( me, tids, NPROC );       // chamada da funcao que classificara a sequencia
	pvm_exit();
	}
     for ( i = 0; i <= m-1; i++ ) {
         for ( j = i; j = 0; j-- ) {
              d = pow ( 2, j ); 		// distancia entre os processadores
// para todos os processadores
dowork(); 
         } // endfor do j
     }  // endfor do i 			
} end do main

Supondo que se queira ordenar n elementos, onde n=2m (2 elevado a m) para algum inteiro m positivo. Observa-se claramente que a complexidade do algoritmo paralelo de cada comando é T(1). Por isso a complexidade deste algoritmo é T(m2 (m elevado a 2)), dados n=2m (2 elevado a m) processadores. 

Seja a seqüência abaixo
 
[ 10, 11, 13, 13, 15, 14, 12, 10, 8, 6, 4, 5, 6, 7, 9, 10 ]
onde n=16. De n=2m (2 elevado a m) tira-se m=4, ou seja, com 4 iterações consegue-se ordenar essa seqüência bitônica. Formam-se dois cubos em que cada vértice figurará como um processador com seu conteúdo.

1º Cubo: P0=10, P1=11, P2=13, P3=13, P4=14, P5=12, P6=10, P7=8
2º Cubo: P8=6, P9=4, P10=5, P11=6, P12=7, P13=9, P14=10, P15=15     
          
	Aplicando o algoritmo e sabendo que a é o valor a ser ordenado que está armazenado no processador corrente; [k+d]a é o valor a ser classificado que está armazenado no processador cujo índice é [k+d].
	Fazendo i=1 j=1 d=2 m=4, pois n=16

k nos exemplos seguintes figurará como como índice de um processador.
k % d é representa o resta da divisão de k por d (distância entre processadores).

No primeiro "se" k é comparado com o resto da divisão dele mesmo por 2.d. Se menor que d, toma-se a decisão seguinte.

No segundo "se" k é comparado com o resto da divisão dele mesmo por 2 elevado a i + 2. Se menor que 2 elevado a i + 1, toma-se a decisão seguinte.
   
Procedendo assim m vezes os processadores ordenarão a seqüência bitônica.

k=0  
Se(0 % 4) < 2
    t =  13 
    se (0 % 8) < 4
         P[2] = max(13, 10)
         P[0] = min(13, 10) 
k=1  
Se(1 % 4) < 2
    t =  13 
    se (1 % 8) < 4
         P[3] = max(13, 11)
         P[1] = min(13, 11)  

k=2  
Se(2 % 4) < 2
    t =  15 
    se (2 % 8) < 4
         P[4] = max(15, 13)
         P[2] = min(15, 13)  

k=3  
Se(3 % 4) < 2
    t =  14 
    se (3 % 8) < 4
         P[5] = max(14, 13)
         P[3] = min(14, 13)  

k=4  
Se(4 % 4) < 2
    t =  12 
    se (4 % 8) < 4
         P[6] = max(12, 15)
         P[4]=min(12,15)  

k=5  
Se(5 % 4) < 2
    t =  10 
    se (5 % 8) < 4
         P[7] = max(10, 14)
         P[5]=min(10,14) 
k=6  
Se(6 % 4) < 2
    t = 8 (2º Cubo) 
    se (6 % 8) < 4
         P[8] = max(8, 15)
         P[6]=min(8,15)

k=7
Se(7 % 4) < 2
     t = P[9] = 6 
     se(7 % 8) < 4
         P[9] = max(6, 14)
         P[7] = min(6, 14)
k=8
Se(8 % 8) < 2
     t = P[10]= 4
     se(8 % 8) < 4
         P[10] = max(4, 15)
         P[8] = min(4, 15)

k=9
Se(9 % 8) < 2
     t = P[11]= 5
     se(9 % 8) < 4
         P[11] = max(5, 14)
         P[9] = min(5, 14)

k=10
Se(10 % 8) < 2
     t = P[12]= 6
     se(10 % 8) < 4
         P[12] = max(6, 15)
         P[10] = min(6, 15)

k=11
Se(11 % 8) < 2
     t = P[13]= 7
     se(11 % 8) < 4
         P[13] = max(7, 14)
         P[11] = min(7, 14)

k=12
Se(12 % 8) < 2
     t = P[14]= 9
     se(12 % 8) < 4
         P[14] = max(9, 15)
         P[12] = min(9, 15)
k=13
Se(13 % 8) < 2
     t = P[15]= 10
     se(13 % 8) < 4
         P[15] = max(10,15)
         P[13] = min(10, 15)

Atingindo o último processador não se faz necessário incrementar k de 1, mas reinicia-se para i=2, j=i e depois j=1. Parando quando j=0.


Complexidade do Bitonic Merge Sort

 	Dados n=2k (2 elevado a k)  elementos não ordenados, uma rede com k(k+1)/2 níveis satisfaz. Cada nível contendo n/2 = 2k-1 comparadores. Por isso o número total de comparadores é
 2k-2 k(k+1). A execução paralela de cada nível requer tempo constante. Observa-se que 
k(k+1)/2 = log n(log n + 1)/2. Portanto o algoritmo tem complexidade Theta(log2 n). 
  	

Ordenação de uma seqüência bitônica de uma forma geral 
 
Supondo que tenhamos uma seqüência bitônica de tamanho n = 2k (2 elevado a k), onde k>0, então k passos de compara-troca são suficientes para produzir uma  seqüência classificada.

	Exemplificando:
Seja a seqüência 
   
[ 20, 21, 23, 23, 25, 26, 24, 20, 19, 17, 16, 12, 12, 11, 10, 9, 8, 9, 10, 11, 12, 12, 13, 14, 15, 18, 19, 20, 21, 22, 23 ] 

onde temos n = 32. Dividindo a seqüência ao meio teremos 16 comparadores. Nota-se que os comparadores são 
	min(a0, a16), min(a1, a17),..., min(a15, a31)  e
	max(a0, a16), max(a1, a17),..., max(a15, a31). 

A técnica é comparar o primeiro elemento da primeira metade com o primeiro elemento da segunda metade, o menor elemento irá para a primeira metade da seqüência original e o segundo o ocupará o lugar do primeiro. A esse processo chama-se de compara-troca.  
Após o processo de compara-troca de posições na primeira iteração, garante-se que nenhum elemento na primeira seqüência é maior que qualquer elemento na segunda seqüência. Procedendo assim recursivamente, em k passos ter-se-á a seqüência original classificada. No caso do nosso exemplo k=5, pois a seqüência é formada por 32 elementos e por definição n=2k (2 elevado a k). 

	Da seqüência original foram geradas duas seqüências bitônicas após a primeira iteração, assim representadas
1ª iteração 
[ 9, 8, 9, 10, 11, 12, 12, 13, 14, 15, 16, 14, 12, 12, 11, 10 ]   2ª seqüência bitônica
[ 20, 21, 23, 23, 25, 26, 24, 20, 19, 17, 18, 19, 20, 21, 22 ]    3ª seqüência bitônica

	Aplicando processo semelhante à 2ª e 3ª seqüências bitônicas, teremos
 2ª iteração
[ 9, 8, 9, 10, 11, 12, 11, 10 ]       4ª seqüência bitônica
[ 14, 15, 16, 14, 12, 12, 12, 13 ]    5ª seqüência bitônica
  
[ 19, 17, 18, 19, 20, 21, 22, 20 ]    6ª seqüência bitônica
[ 20, 21, 23, 23, 25, 26, 24, 23 ]    7ª seqüência bitônica  

 
3ª iteração
[ 9, 8, 9, 10 ]            8ª seqüência bitônica
[ 11, 12, 11, 10 ]         9ª seqüência bitônica

[ 12, 12, 12, 13 ]        10ª seqüência bitônica
[ 14, 15, 16, 14 ]        11ª seqüência bitônica
  
[ 19, 17, 18, 19 ]        12ª seqüência bitônica 
[ 20, 21, 22, 20 ]        13ª seqüência bitônica

[ 20, 21, 23, 23 ]        14ª seqüência bitônica
[ 25, 26, 24, 23 ]        15ª seqüência bitônica  

4ª iteração
[ 9, 8 ]                  16ª seqüência bitônica  
[ 9, 10 ]                 17ª seqüência bitônica  

[ 11, 10 ]                18ª seqüência bitônica  
[ 11, 12 ]                19ª seqüência bitônica  

[ 12, 12 ]                20ª seqüência bitônica  
[ 12, 13 ]                21ª seqüência bitônica

[ 14, 14 ]                22ª seqüência bitônica  
[ 16, 15 ]                23ª seqüência bitônica
  
[ 18, 17 ] 	          24ª seqüência bitônica  
[ 19, 19 ]                25ª seqüência bitônica 

[ 20, 20 ]                26ª seqüência bitônica  
[ 22, 21 ]                27ª seqüência bitônica

[ 20, 21 ]                28ª seqüência bitônica
[ 23, 23 ]                29ª seqüência bitônica

[ 24, 23 ]                30ª seqüência bitônica
[ 25, 26 ]                31ª seqüência bitônica  
 


5ª iteração - Final
 
[ 8 ]  
[ 9 ]                  

[ 9 ] 
[ 10 ]                

[ 10 ] 
[ 11 ] 
             
[ 11 ]
[ 12 ]              

[ 12 ] 
[ 12 ]
              
[ 12 ] 
[ 13 ]              

[ 14 ] 
[ 14 ]             

[ 15 ]
[ 16 ]             
  
[ 17 ] 
[ 18 ] 
	            
[ 19 ] 
[ 19 ]             

[ 20 ] 
[ 20 ]            

[ 21 ] 
[ 22 ]            

[ 20 ] 
[ 21 ]            

[ 23 ] 
[ 23 ]            

[ 23 ] 
[ 24 ]            

[ 25 ] 
[ 26 ]
           
Portanto, após 5 iterações a seqüência original fica ordenada conforme queríamos provar.