I've only briefly skimmed the paper, but here's something I've come up with, based on what I read, that might or might not be the same as what they've said, but I think "has legs":

* Randomly choose some fixed sized subset of the data and sort it;

* Based on that, deduce the distribution of the data;

* Based on that, create a destination array, and copy things from the input to roughly the expected right place in the output;

* Run around and fix things.

When sorting numbers, that feels like it has a chance of running quite quickly. For other objects with some other comparison function, not sure how it would work.