can we prove that the algorithm to extarct the median must partition the set?

Question

Extracting the median of, say, 51 element, consists of splitting the 51 in a H(ead) group of 25, followed by the median, followed by a T(ail) of 25. All the algorithms that I know end up with the additional property that H and T are such that [min(H), max(H)[ and ]min(T), max(T)] do not overlap.

Is this additional property proven mandatory (I guess yes) ? where can I find the proof (I guess it have been done for long) ?

(This is only for the sake of love for algorithms)

Answer 1

If the elements are not unique, then the two sets can in fact overlap (imagine a list of 51 identical elements....)

If the elements are unique then the non-overlapping property is easy to prove by contradiction. From the partitioning of unique elements we have:

• x < median for all x in H
• y > median for all y in H

Suppose H and T do overlap. Then we have:

• x >= y for some x=max(H), y=min(T)

But that implies:

• x >= y > median

Which is a contratiction because we aleady know x < median. Hence the two sets cannot overlap.