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.

• Also posted on Stack Overflow. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. – Raphael Jun 13 '15 at 15:03
• So you are aware that you are looking for a selection algorithm and that selecting a single rank statistic can be done in $O(n)$ time. Have you looked at the algorithms that facilitate that and checked if you can modify them to find more than one rank statistic with little extra cost? (By the way, afaik nobody uses linear-time selection algorithms in practice -- Quickselect is usually faster.) – Raphael Jun 13 '15 at 15:07
• Also, $O(n \log k)$ seems to be impossible; you'll need time $\Omega(k)$ just to assemble the result. An attainable bound may be $O(k + n \log k)$. – Raphael Jun 13 '15 at 15:08
• Could you add some sample cases? I'm not clear about what does "k equal parts" mean. – coderz Jun 13 '15 at 15:18
• @coderz If the array is: [7,1,3,4,5,8,2,6,9]. And let's say k=3. Then we want to find the items 3 and 6. if k=2 then we want to find 4. And so on.. Hope it's clear! – Jaja Jun 13 '15 at 15:41

Initially assume that k is odd.

Algorithm:

1. Find the median of the unsorted array. This can be done using Selection Algorithm in O(n) time.
2. Recursively find the median of the two partition thus obtained.

Time complexity: O(nlog(k))

Analysis:

In each recursive step, you double the items obtained so far. So the number of steps would be log(k). Also in each recursive step time taken is O(n). Thus total time taken would be O(nlog(k))

The case in which k is even can be solved in similar fashion.

I assume that $k = 2^m$ ($m \in \mathbb{N}$) and $k \le n$.

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

1. Select the median of the array $A$ and use it to partition the array into $A_l$ and $A_r$
2. 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.