Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2).
We want to recursively merge the odd-indexed elements from each list: merge $a_1, a_3,...,a_{n-1}$ with $b_1, b_3,...,b_{n-1}$; this will form the list $c_1, c_2,...c_n$. Then do the same for the even-indexed elements: merge $a_2, a_4,...,a_n$ with $b_2, b_4,...,b_n$ to form $d_1, d_2,...,d_n$.
Then consider the shuffled list $c_1, d_1, c_2, d_2,...,c_n, d_n$ and do the following:
$$ \texttt{for } i:= 1\texttt{ to } n-1 \texttt{ do}\\ \hspace{4ex} \texttt{if } (d_i > c_{i+1}) \texttt{ then }\\ \hspace{8ex} \texttt{interchange them}\\ $$
How would I set up and solve a recurrence for the running time and the merge sort?
