i need help urgent Option $1$

$($Using MPI environment. Modified version of Q $3\mathrm{.}26,$ P$.147)$

Q: Serial odd$-$even transposition sort of an n$-$element list can sort the list in considerably fewer than $n$ phases. As an extreme example, if the input list is already sorted, the algorithm requires $0$ phases.

$(1)$ Write a serial odd$-$even transposition sort program.

$(2)$ Modify the serial odd$-$even transposition sort program, by including a serial Is$\_$sorted function that determines whether a list is sorted, so that it checks whether the list is sorted after each phase.

$(3)$ Write a parallel odd$-$even transposition sort program.

$(4)$ Find the speedups and efficiencies of the parallel odd$-$even sort. Does the program obtain linear speedups? Is it strongly or weakly scalable?

Hint:

The odd$-$even transposition sort is a variation of bubble sort. Like in bubble sort, elements of a list are compared pairwise and swapped when necessary. However, these compare$-$swaps are done in two phases: odd and even.

Option $2$:

$($Using OpenMP environment. Modified version of Q $5\mathrm{.}3,$ P$.268)$

Q: Count sort is a simple serial sorting algorithm that can be implemented as follows:

Hint:

The basic idea here is that for each element a$[$i$]$ in the list a$,$ we count the number of elements in the list that are less than a$[$i$].$ Then we insert a$[$i$]$ into a temporary list using the subscript determined by the count. There is a slight problem with this approach when the list contains equal elements, since they could get assigned to the same slot in the temporary list. The code deals with this by incrementing the count for equal elements based on the subscripts.

If both $a[i]==a[j]$ and $a[j]a[i]j,$ then $we$ count $a[j]as$ being "less than" $a[i].$ After the algorithm has completed, $we$ overwrite the original array with the temporary array using the string library function memcpy.

$(1)Ifwe$ try $to$ parallelize the for i loop $(the$ outer loop$),$ which variables should $be$ private, and which should $be$ shared?

$(2)Ifwe$ parallelize the for i loop using the scoping you specified $in$ the previous part, are there any loop$-$carried dependences? Explain your answer.

$(3)$ Can $we$ parallelize the call $to$ memcpy? Can $we$ modify the code $so$ that this part $of$ the function will $be$ parallelizable?

$(4)$ Write a parallel Count sort program.

$(5)$ How does the performance $of$ your parallelization $of$ Count sort compare $to$ serial Count sort? Find the speedups and efficiencies.