Labs 9-10. The Odd-Even Sorting Algorithm

---

Task 1. Develop the method MPI_Compare_Exchange().

- Use some methods for sorting and merging from the previous programs.

- Develop a MPI method exchange e.g. int MPI_Exchange( int n, double *a, int rank1, int rank2, MPI_Comm comm )
a. Get the rank and size of comm.
b. If rank == rank1 them
 i. Send the array a to rank2
 ii. Receive the array b from rank2
 iii. Merge the array a and b
 iv. a keeps only the first part of the merged array c. 
c. If rank == rank2 them
 i. Receive the array b from rank1
 ii. Send the array a to rank1
 iii. Merge the array a and b
 iv. Keep in a only the second part of c.
- Test this method as follows:
a. Scatter an array on to processor
b. Exchange between Processor 0 and Processor 1. 
c. Gather the arrays onto Processor 0.
d. See whether the elements are sorted out.

---

Task 2. Develop the method int MPI_Odd_even_sort().

1. Start from the MPI_Compare_exchange() routine after you test it and see whether it works to sort with 2 processors.
2. Bring the code for odd-even sort from some slide in the lecture notes.
3. Organise the code as a MPI function.
4. Test the code on various number of processors

---

Task 3. Implement and test the MPI routine int MPI_Is_sorted(int n, int * array, int root, MPI_Comm comm);

1. Gather the first elements of the arrays to the root.

2. Gather the last elements of the arrays to the root.

3. If processor root then test first[i+1] vs last[i].

a. if first[i+1] < last[i] for some i = 0,1,…, size-2 then the answer is negative

4. Bcast the answer to All.

5. Then put together the final bits for the odd-even sort.

---