Why half of the medians are greater than the median of medians?

Question

I already saw similar question Counting elements that are greater than the median of medians but I couldn't find my answer in there.

CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers. This is the algorithm:

1. Divide the $n$ elements of the input array into $\lfloor n/5\rfloor$ groups of 5 elements each and at most one group made up of the remaining $n$ mod 5 elements.
2. Find the median of each of the $\lceil n/5\rceil$ groups by first insertion-sorting the elements of each group (of which there are at most 5) and then picking the median from the sorted list of group elements.
3. Use SELECT recursively to find the median $x$ of the $\lceil n/5\rceil$ medians found in step 2. (If there are an even number of medians, then by our convention, $x$ is the lower median.).
4. Partition the input array around the median-of-medians $x$ using the modified version of PARTITION. Let $k$ be one more than the number of elements on the low side of the partition, so that $x$ is the $k$th smallest element and there are $n-k$ elements on the high side of the partition.
5. If $i = k$, then return $x$. Otherwise, use SELECT recursively to find the $i$ th smallest element on the low side if $i < k$, or the .$(i-k)$th smallest element on the high side if $i > k$.

My problem is the steps 2 and 3. It claims

at least half of the medians found in step 2 are greater than or equal to the median-of-medians x.

Some thing that I can't understand very well. May be there is a misunderstanding in the median-of-median term. What I understand of the median-of-median is in the following:(Every group of five elements is sorted increasing)

There is a list $A_1 \cdots A_{75}$ of input array

Step1: Sort every group of five elements $$\overbrace{A_1A_2A_3A_4A_5}\overbrace{A_6A_7A_8A_9A_{10}}\overbrace{A_{11}A_{12}A_{13}A_{14}A_{15}} \cdots \overbrace{A_{71}A_{72}A_{73}A_{74}A_{75}}$$ step 2 of algorithm (get medians) $$ \overbrace{A_3 A_8 A_{13} A_{18}A_{23}}\overbrace{A_{28}A_{33}A_{38}A_{43}A_{48}}\overbrace{A_{53}A_{58}A_{63}A_{68}A_{73}} $$ Then repeat recursively (median of medians) $$ \overbrace{A_{13},A_{38},A_{63}} $$ $$ x = A_{38} $$

From what I understand, in the last level we can guarantee that $A_{63}$ is greater than $x$. In step 2 only $A_{68}, A_{73}$ are greater than $A_{63}$ so they are greater than $x$ as well. Since in step 2 $A_{43}, A_{48}$ are greater than $A_{38}$ So at most five elements among 15 elements in step 2 are greater than the $x$. Then why CLRS claims that half of the medians in step2 are greater than $x$?

thanks in advance.

---

update

If the algorithm of finding median of medians is not what I did above, How can I find the median of medians of step2 in $O(n)$?

Answer 1

Because $x$ is the median of all the $\lfloor n / 5 \rfloor$ medians obtained in Step 2, it is smaller than or equal to half of those medians by definition of median. See the figure below (from CLRS, the 3rd edition; Figure 9.1).

The problem with your example is that you are finding the median-of-medians $x$ recursively, however, without completing all the recursive steps. You should not stop at Step 3 (the "median of medians" step) in the recursion. Continue the remaining steps. In particular, in Step 4, you will use the "Partition" procedure to establish relationships between the medians obtained in Step 2 and this median-of-medians $x$.

For your added problem: You find it recursively. Why is the time complexity $O(n)$? Well, you can follow the analysis in CLRS.

Answer 2

The answer is easy: because the median-of-medians is... the median of the medians. (By definition, the median of a set of values is larger and smaller than half of these values.)

But the important property in the design of the algorithm is that the median-of-median is also guaranteed to be larger and smaller than a quarter of the values in the array (not just the medians), so that it is a good partitioning pivot. (This guarantees that the number of remaining elements after a partition decreases exponentially.)