Quick sort with $K-1$ pivots

I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $$k−1$$ pivots to partition an array of unique numbers into $$k$$ classes? My goal is to demonstrate that this multiary partitioning can be achieved in $$O(n \log k)$$ time, ensuring that all classes are approximately of the same size (to within 1).

I found this paper https://cs.stanford.edu/~rishig/courses/ref/l11a.pdf

but it doesn't seem to talk about how to go about partitioning the array into nearly equal. Note: I am just interested in selecting the pivots not the partition algorithm

I did try finding the $$n/k^{\text{th}}, 2n/k^{\text{th}} \ldots$$ smallest element in the array and using them as pivots but the complexity isn't coming right (as each element can be found using BFPRT algorithm in $$O(n)$$ therefore total complexity would be $$O(nk))$$
Any Insights will be appreciated.

Hint: Suppose $$k$$ is a power of two at first, for simplicity. Find the $$n/2$$th element in the array. Then.... (you fill in the next part)
• @HaaziqJamal You went wrong in the number of levels. There will be only $O(\log k)$ levels (in each recursive call, you halve the number of pivots you are looking for). Feb 17 at 13:13