Suppose we have mysterious machine which return median $m$ of given set $S$ and set $S/\{m\}$ in constant time, where $S/\{m\}$ denotes the difference of $S$ and element $m$. Prove that we can sort any list of $n$ elements in linear time using such machine. (extra space is allowed)

Here is my idea, which works intuitively correct, but could not prove it mathematically:

Create a new array with $n$ elements and assign median $m$ of original set $S$ to the middle of array. In each iteration, we put new median of $S/\{m\}$ into the right or left of recently used element: if it was on the left, put new median on the left of that element, and similarly for rightmost element. However, I could not think on how mathematical proof would be possible here. Would welcome your comprehensive proofs for this problem.

Note: If number of elements is even, median is defined as smaller middle number.

  • $\begingroup$ It is enough to prove that the extra array $A$ starts sorted and if $S$ and $A$ are non-empty the median $m$ of $S$ is either $m\leq\min(A)$ or $\max(A)\geq m$. You can prove this by induction. After the first step $A$ contains one element. So, it is sorted and the other condition is due to $\leq$ being a total order. Assume that the condition is true after $k$ steps and now you take the median $m$ of $S$, which is the list $S$ after $k$ steps and add it to $A$ on the side that it corresponds. So, now we are at step $k+1$. The condition that $A$ is sorted is automatic. ... $\endgroup$
    – plop
    Oct 20 '20 at 18:13
  • 1
    $\begingroup$ Where did you encounter this? Always provide proper attribution for all copied material. $\endgroup$
    – D.W.
    Oct 20 '20 at 19:34
  • 1
    $\begingroup$ @D.W. This is original problem created by my professor. $\endgroup$
    – Snowflake
    Oct 20 '20 at 19:37
  • 1
    $\begingroup$ Please edit your question to credit your professor, then. $\endgroup$
    – D.W.
    Oct 20 '20 at 19:37
  • 2
    $\begingroup$ @AnarRzayev I have deleted your unnecessary remarks here. Please be aware that we cannot know that your professor prefers to remain anonymous before you tell us this. In general, we try to encourage people to post the source of their problems here, as this helps providing attribution to everyone who wants attribution. This is not relevant in all cases, but that is hard to tell if we don't ask. $\endgroup$
    – Discrete lizard
    Oct 21 '20 at 6:05

This answer supposes that you know $n$ in advance, but can be adapted to the general case.

  n ← length(S)
  T ← {1,...,n}
  A ← new array of length n
  repeat n times:
    S, m_S = extract_median(S)
    T, m_T = extract_median(T)
    A[m_T] = m_S
  end repeat
  return A

The idea here is that repeatedly extracting the median will output the elements of $S$ sorted in some fixed order which depends only on $n$. We can determine the order by running the same process on the set of indices $\{1,\ldots,n\}$.


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.