Sorting an already k-sorted array

Question

Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

We say that an array $A[1...n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$, such that the elements in each block are larger than the elements in earlier blocks, and smaller than the elements in later blocks. The elements within each block need not to be sorted. For example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

a) Describe an algorithm that $k$-sorts an arbitrary array in time $O(n\log k)$.

b) Prove that any comparison-based $k$-sorting algorithm requires $\Omega(n \log k)$ comparisons in the worst case.

c) Describe an algorithm that completely sorts an already $k$-sorted array in time $O(n \log(n/k))$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how to solve this.

For a) my teacher said that we need to find the median and then do something like what quicksort does on finding a good pivot. I was searching over the net and I had the idea to put the $k$ first elements as leafs of a min-heap and then take the min element and with the next element of the array fill each block with $n/k$ elements, but it fails with the input: $8, 7, 6, 5, 4, 3, 2, 1$

Clearly, b) is something like proving that any algorithm based in comparisons takes $O(n\log n)$. Maybe $\log k$ is because we only need to sort each block with $n/k$ elements, that means for each block we need to do $O(n/k \times\log k)$ $k$ times, so we could actually do it in time $O(k\times n/k \times \log k) = O(n\log k)$

For c) I'm not really sure, but I can take all the elements of each block and put them as leafs of a min-heap $-$ which gives $O(\log n/k)$ $-$ and then sort them, which I think would take $O(n \log n/k)$.

Thanks in advance.

Answer 1

You have the right idea but I think you are overthinking it a bit.

For a), your teacher had a good hint. I think there is a simpler solution than the way you are going. As a further hint, notice that if $k=2$, the problem is solved after 1 round of quicksort (with linear median-finding). You have two equal-sized subarrays, where the left is smaller than the right. Can you extend this to $k=4$? Then, can you extend it to arbitary $k$?

b) I think you have the right intuition, but this argument is not formal yet. Recall the original proof of the sorting lower bound, where you argue that you need $n\log n$ comparisons to get $n!$ permutations. Can you extend that to this case? How many permutations are required when we don't need to fully sort?