Odd-even transpose is a
parallel sorting algorithm. It is somewhat of a parallel
bubble sort. The idea is to assign a
processor to each of the n elements to sort. Then, on odd timesteps, odd numbered processors compare their data with the processor on their right, and exchange elements if the element on the odd processor is greater than the element of the processor on its right.
On even timesteps, the same process is followed, except each odd processor compares and exchages data with the processors to their left, instead of right.
This algorithm will run O(n) steps given n elements and n processors. This is better than the serial O(n log(n)), but is not work optimal.
The algorithm is naturally suited for parallel computers with a linear array topology.