Odd-even Transposition Sort

Recall the operation of a bubble sort algorithm. For $n$ elements, a first phase iterates through the elements, comparing and exchanging neighbors, with $n-1$ operations. After the first phase the largest element will have "bubbled" to the end of the array.

Since the largest element appears at the end of the array after the first phase, the second phase need only iterate $n-2$ times. The bubble sort however takes $O(n^2)$ sequential steps.

The odd-even transposition sort makes use of a pipelining technique to ultimately run many phases of the bubble sort in parallel.

The second phase of the bubble sort algorithm can begin after the second iteration of the first phase.

The third phase can begin after the fourth iteration, the fourth phase after the sixth iteration and so on.

In effect each parallel computational step can pair off either the odd or even neighboring pairs.

Assuming $n$ is an even number.

Processor $P_i$, $i$ is odd: send(A, Pi-1); recv(B, Pi-1); if(A<B) A=B; if(i<=n-3){   send(A, Pi+1);   recv(B, Pi+1);   if(A>B) A=B;}

Processor $P_i$, $i$ is even: recv(A, Pi+1); send(B, Pi+1); if(A<B) B=A; if(i>=2){   recv(A,Pi-1);   send(B,Pi-1);   if(A>B) B=A;}