I suppose you could pick the bounds by sampling: pick m random elements, sort them, and use those as the upper bounds. Better yet, pick km random elements, sort them, and use every k'th one as an upper bound. But the author's intention is that the number of classes is a (large!) fraction of the number of elements, so this would give you O(n log n) overall complexity, missing the point entirely.
I note that the classification algorithm, if run on already-sorted input, puts the classes in reverse order. If the classes are small, this doesn't matter, but if they were bigger, it would be worth using the TimSort trick of checking for runs of increasing elements and just flipping them.
I also note that this algorithm involves making three passes over the data: one to count the number of elements in each class, one to classify elements (this pass involves random access), and another to sort the classes. No worse than quicksort, but not ideal for an external sort, and maybe not too cache-friendly.