Algorithm OddEvenMerge$($A$,$ B$,$ C$)$:

Input: Two sorted arrays, A $=[$a$1,$a$2,...,$an$]$ and B $=[$b$1,$b$2,...,$bn$],$ and an

empty array, C$,$ of size $2$n

Output: C$,$ containing the elements from A and B in sorted order

Let O$1[$a$1,$a$3,$a$5,...,$an$1]$

Let O$2[$b$1,$b$3,$b$5,...,$bn$1]$

Let E$1[$a$2,$a$4,$a$6,...,$an$]$

Let E$2[$b$2,$b$4,$b$6,...,$bn$]$

Call OddEvenMerge$($O$1,$ O$2,$ O$),$ where O $=[$o$1,$ o$2,...,$ on$]$ Call OddEvenMerge$($E$1,$ E$2,$ E$),$ where E $=[$e$1,$ e$2,...,$ en$]$ Let C $[$o$1,$e$1,$o$2,$e$2,...,$on$,$en$]$

for i $1$ to n do

Do a compare$-$exchange of C$[2$i $1]$ and C$[2$i$]$

return C

Algorithm $8\mathrm{.}13$: Odd$-$even merge.

are out of order, as an atomic action called a compare$-$exchange. For example, she could use bubble$-$sort $($Algorithm $5\mathrm{.}20)$ to sort A$,$ since this algorithms is data$-$oblivious when implemented using the compare$-$exchange primitive. But this would require O$($n$2)$ time, which is quite inefficient for solving the sorting problem. An alternative is to use the odd$-$even merge$-$sort algorithm, which is the same as the merge$-$sort algorithm given above, except that the merge step is replaced with the merge method shown in Algorithm $8\mathrm{.}13.$ Argue why the odd$-$ even merge$-$sort algorithm is data$-$oblivious, and analyze the running time of the resulting sorting algorithm.