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/e-e/o pair c time if operands are local; ignore all other local computation