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.