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
Apply compare-exchange (Pj, Pj+1) //Operation is executed in parallel
Else // Even phase
Apply compare-exchange(Pj, Pj+1) //Operation is executed in parallel
Let us take an example and illustrate the odd-even transposition algorithm.
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.