You do not need to sort for the preprocessing based solution, you only need a K-way partition, which if I'm not mistaken, it can be done in two linear passes. I

You do not need to sort for the preprocessing based solution, you only need a K-way partition, which if I'm not mistaken, it can be done in two linear passes. I don't remember if it can be done in place easily though.