Find a recurrence relation for merging of sublists of an array
The mistake is when converting $O(n)$ to $O(2^m)$, and then varying $m$. In fact, $n$ is constant here and $m$ changes. So the recurrence relation is $T(m) = T(m/2) + O(n)$, whose solution is $T(m) = O(n\log m)$. Substituting $m = \log n$, we obtain $O(n\log\log n)$.