>The downside to radix sort is that is just looks at bytes. If you had some deep and semantically meaningful ordering defined over your type, (or, like, a pointer) that's great but we're sorting by its bytes.
See Fritz Henglein's "Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" paper for a nice way to extend radix sort's runtime to arbitrary meaningful orderings:
See Fritz Henglein's "Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" paper for a nice way to extend radix sort's runtime to arbitrary meaningful orderings:
http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...
Beginning of a haskell implementation here: http://ekmett.github.io/discrimination/index.html . Might be doable in rust as well.