Algorithm: Odd-Even Transposition
//Input: N numbers that are in the unsorted form
//Assume that element bi is assigned to pi
for I=1 to N
{
If (I%2 != 0) //i.e Odd phase
{
For j=1,3,5,7,..................2*n/2-1
{
Apply compare-exchange (Pj, Pj+1) //Operation is executed in parallel
}
}
Else // Even phase
{
For j=2,4,6,8..................2*(n-1)/2-1
{
} I++
}
Apply compare-exchange(Pj, Pj+1) //Operation is executed in parallel
}
Let us take an example and illustrate the odd-even transposition algorithm.
Analysis
The above algorithm needs one „for loop? starting from I=1 to N, i.e. N times and for every value of I, one „for loop? of J is implemented in parallel. Thus, the time difficulty of the algorithm is O (n) as there are total n phases and each phase executes either odd or even transposition in O(1) time.
Example