Yes, I'm more familiar with the issue in the context of strings or lists. Your example of strings like "'x' * 10_000 + str(i)" looks like something I almost certainly used before as counterexample to someone's time complexity claim :-)

I the context of multi-criteria sort I might not have thought of it before, I guess because you usually don't have many criteria. But now this made me think we can take even more advantage of the existing tuple_elem_compare.

I the context of multi-criteria sort I might not have thought of it before, I guess because you usually don't have many criteria. But now the optimized tuple_elem_compare makes me think we can take even more advantage of it.

I think those type-specific optimized comparison functions are what I left out when I previously read the sort, that's why it was new to me. I just saw you also use powersort's merge strategy now. Kinda sad, I had seen you lament that your own strategy "remains hard to grasp why it's always correct now", while I think it's rather straightforward and had considered adding a little explanation in the doc.

Bucket sort is a name I considered, but I wrote two, so named them after their implementation (groupsort first used itertools.groupby).