Homework Problem #1

Analyze the complexity of the Odd/Even Interchange Sort (Parallel Bubble Sort):
Given array A[n], exchange odd and even indexed pairs if not ordered, then exchange even/odd pairs if not ordered, then repeat until sorted

Analyze with the CTA model (i.e. for P  number of processors, lambda  cost of communication between processors, d  degree of the tree if necessary), and charge the o/ee/o pair c time if operands are local; ignore all other local computation
The homework is due before class 4/10/07. Email a copy of your analysis to nkuchta at cs with the subject '524P HW1'.