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?

  • $\begingroup$ Easy. Finding the median is $\Theta(n)$, therefore sqrt(n) >= cn, and since we can sort in O(n^2 / sqrt(n)), we can sort in O(n). $\endgroup$
    – gnasher729
    Jan 20 '20 at 18:51
  • 2
    $\begingroup$ "In a hypothetical world, we have a machine that ..." actually means that "We are given a hypothetical machine that ..., hence this world becomes a hypothetical world." That is, we can use whatever we can do besides using this machine. In particular, you can use the partition technique. $\endgroup$
    – John L.
    Jan 20 '20 at 21:18

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'$) {

  1. If $r-l<2$ then manually update $A'[l...r]$ and return; $\leftarrow$ Basecase.
  2. Let $m:=$Median($A,l,r$); $\leftarrow$ Compute a median in $O(\sqrt{n})$-time using the oracle.
  3. Let $A'[(l+r)/2]:=m$;
  4. Median-Merge-Sort($A,l,(l+r)/2,A'$);
  5. 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.

  • 1
    $\begingroup$ How does the proposed algorithm works on the input [3, 2, 1]? In the first step it finds the median to be 2 and then recursively solve on the first half [3] and second half [1] which belongs to the base case, so the output would be [3, 2, 1] which is not sorted. $\endgroup$ Sep 18 '20 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.