Selecting k-1 items that divide a sorted array to k equal parts Given an unsorted array of $n$ integers, I need to find an $O(n \log k)$ algorithm that finds the $k-1$ items that divide the sorted array to $k$ equal (up to $\pm 1$ items) parts.

For example, if $k=3$, the items we want would be at indices $n/3$, $2n/3$ in the array after we sort it.

I know that you can select those items in $O(nk)$ but I can't think of how to improve that $k$ to $\log k$. I'd appreciate any help.
I assume that $k = 2^m$ ($m \in \mathbb{N}$) and $k \le n$.

Here is a recursive (divide-and-conquer) algorithm:


Select the median of the array $A$ and use it to partition the array into $A_l$ and $A_r$
Do the same thing above recursively on $A_l$ and $A_r$.


It is easy to see that the depth of the recursive is $O(\lg k)$. Unfolding the recursive tree, you will find that at each depth (i.e., recursion), the non-recursive cost is $O(n)$ for median-selection and partition.



Note that if $k = n$, the algorithm above is the QuickSort algorithm with medians as pivots.