= Solution
Recursively partition into equal halves by rank, keeping the selected median in the lower half:
``
quantiles(A,k):
if length(A) == k:
return [maximum(A)]
p = select the (length(A)/2)-th smallest element of A
L = all elements of A at most p
R = all elements of A greater than p
return quantiles(L,k) followed by quantiles(R,k)
``
All elements are distinct, so both halves have exactly $|A|/2$ elements. Since $|A|/k$ remains a power of two, every internal split occurs at a rank divisible by $k$.
For correctness, the desired ranks in the lower half are $k,2k,\ldots,|A|/2$. In the upper half they are the same local multiples of $k$, shifted by $|A|/2$. These are exactly all desired global ranks. At a leaf of size $k$, its maximum is its sole requested local rank. Induction therefore proves that the output contains every requested <order statistic>, in increasing order, including the original maximum. There is no separate internal-node output of `p`, which would duplicate a rank already supplied by the lower subtree.
Use a worst-case linear-time <selection algorithm> and linear partitioning. The <divide-and-conquer algorithm> has
$$
T(n,k)=2T(n/2,k)+\Theta(n)\quad(n>k),\qquad T(k,k)=\Theta(k).
$$
There are $\log_2(n/k)$ internal levels, each with total work $\Theta(n)$, and $n/k$ leaves with total work $\Theta(n)$. Since the source assumes $n/k\geq2$, the running time is
$$
\boxed{\Theta\bigl(n\log(n/k)\bigr)}.
$$
This is <multiselection by balanced rank partitioning>. In-place selection and partitioning can use the original array; the output has $n/k$ values. The multiselection recursion has depth $O(\log(n/k))$; the selection routine contributes its own auxiliary storage.
Back to article page
