Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$ In a hypothetical world, we have a machine that can find median of $n$
  numbers in $O(\sqrt{n})$. (Of course this machine is not real).
  
  Can we use this machine to sort an array in $O(n)$?


I don't know how can I approach these type of questions which have a wrong statement as given. I know if the machine also partitions the array when finding the median, we can sort the array in $O(n)$ using $T(n) = 2T(n/2) + O(\sqrt{n})$. 

But the question didn't say anything about partitioning. So if we assume that it doesn't change the array in any way and just finds the median, Can we use this machine to sort the array in $O(n)$ or not?
We don't have to merge two sorted arrays, if we can simply compute the median information and store it in an auxilliary array; by definition, a median of an array $A[l...r]$ is the element in $A[(l+r)/2]$ when $A$ is in sorted order. Given this definition, we can simply use mergesort-style divide and conquer, while keeping track of another array $A'$ with medians of subarrays of $A$; in the end, $A'$ will be the sorted version of $A$:
Procedure Median-Merge-Sort($A,l,r,A'$) {

If $r-l&lt;2$ then manually update $A'[l...r]$ and return; $\leftarrow$ Basecase.
Let $m:=$Median($A,l,r$); $\leftarrow$ Compute a median in $O(\sqrt{n})$-time using the oracle.
Let $A'[(l+r)/2]:=m$;
Median-Merge-Sort($A,l,(l+r)/2,A'$);
Median-Merge-Sort($A,(l+r)/2+1,r,A'$);

}
The overall running time is $T(n)=2T(n/2)+O(\sqrt{n})$, which solves to $O(n)$ using master's theorem. This also tells us we cannot have a median-finder working in $O(\sqrt{n})$ on the comparison model, otherwise we can sort in linear time, which violates the sorting lower bound on the comparison model.