I played with faster sorting in Go, and it’d be cool to work more with the ideas here. I did one thing for simple binary sorting using ints-from-strings, but more is possible.
The trick to bail out in situations where the abbreviated key has low entropy is really clever.
Would also be interesting to play with stable sorts, either MSD or by sorting string keys then sorting equal keys by their original indices into the array. Downside of an out-of-place sort in Go is that allocating temp space means more GC work, though.
Could also be useful to have a “group identical strings” operation where you use a hash value (as in hashtable hash not crypto hash) as the abbreviated key. You should get good entropy from the abbreviated-sorting stage even if lots of the strings have shared prefixes then, and you can still do counts and logarithmic exact-match searches with grouping.
Anyway, lot of basic algos that it’d be neat to have. Matter of tuits and of course matching them to practical use cases. :)