It's a little surprising that this works at all, since the partitioning step in the radix sort is itself the same kind of sharding operation. But I guess that's because it allows for working on smaller pieces at a time that fit in whatever cache they need to.

> Python can't really reserve space for lists, but pretend `reserve` did that anyway.

FWIW, you can pre-fill a list with e.g. `None` values, and then replacing those values won't cause resizes or relocations (of the list's memory - the elements are still indirected). But of course you'd then need to keep track of the count of "real" elements yourself.

But of course, tricks like this are going to be counterproductive in Python anyway, because of all the indirection inherent in the system. They'll also get worse if you actually do have objects (unless perhaps they're statically, constantly sized, and in a language that can avoid indirection in that case) with a "group ID" attribute, rather than integers to which you can apply some hash function. Some test results, trying to approximate the Rust code in Python but with such objects:

https://gist.github.com/zahlman/c1d2e98eac57cbb853ce2af515fe...

And as I expected, the results on my (admittedly underpowered) machine are terrible (output is time in seconds):

    $ ./shard.py 
    Naive: 1.1765959519980242
    Presized: 2.254509582002356
    Library sort / groupby: 6.990680840001005
    Simple radixing first: 3.571575194997422

It's important to understand the domain. For Pythonistas, simple really is better than complex. And identifying the bottlenecks and moving them to a faster language is also important (Numpy isn't successful by accident). The naive result here is still, if I'm understanding the graphs right, dozens of times worse than what any of the Rust code achieves.

(Edit: merely "several" times worse. I forgot that I told `timeit` to run 10 iterations over the same input, so each test processes ~10M elements.)