What is a fast algorithm for partitioning an array into $k$ subsets $A_1<\dots<A_n$?
You can do $O(n \log k)$ by finding $mk/2$-order statistic, partitioning the array into two parts of size $mk/2$ and recursing on each side until $k = 1$. You get the recurrence on running time $T(m, k) = 2 T(m,k/2) + \Theta(m k)$ and $T(m, 1) = \Theta(1)$, which solves to $T(m,k) = O(m k \log k) = O(n \log k)$.