Selecting k-1 items that divide a sorted array to k equal parts
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.