algorithms – Recursive Selection of Pivot from an Array


Suppose we have an array of integers $A$ of length $n$, which is assumed to be multiple of 5 for convenience in the discussion below. Now we try to pick a pivot $x$ from $A$ such that $x$ can divide $A$ into two relatively balanced subsequences. Below is the procedure:

  1. Divide $A$ into groups of 5 elements each: for each $1leqslant i leqslant n/5$, the $i$– th group should be
    $$
    A(5(i-1)+1), A(5(i-1)+2), A(5(i-1)+3), A(5(i-1)+4), A(5(i-1)+5)
    $$
  2. Find the median of each group directly and denote the median for the $i$-th group by $C_i$.
  3. Recursively select the median $x$ out of $C_1,…,C_{n/5}$.

Also, it is said that

If $x$ is the pivot picked, then both the number of elements smaller than $x$ and the number of elements larger than $x$ is at least $3n/10$.

My question is, how is this lower bound derived? Any formal proofs, ideas, or hints will be greatly appreciated! 🙂