Design: kth quantiles, multiary Quicksort. In Quicksort a pivot element

partitions an array of numbers to those smaller than the pivot and those larger

than the pivot $($assume for simplicity that all numbers are unique$).$ Consider

a multiary version of Quicksort, where k $1$ pivots are chosen to partition the

numbers to k classes analogously to the standard Quicksort. Show that such

multiary partitioning can be produced in O$($n log k$)$ time so that the all classes

are of the same size $($to within $1).$ Hint. You can assume selection in linear time.

Aim to reveal one of the final pivots and then recurse. Which pivot should you

reveal first?