Why half of the medians are greater than the median of medians?
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. 743
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)$? 743