# 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! 🙂 Posted on Categories Articles