3 ms·
> A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time. Nitpick, but you can only sort
by inoop 8y ago
> A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time.
Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers).
> Sadly, this information is not well distributed among software engineers in industry.
Agreed, although you may be interested to know most software 3D rendering engines in the 90's used American flag sorting variants to efficiently implement the painter's algorithm.
- frankmcsherry 8y ago> Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers). It is more subtle than this. Top-down radix sort (which discrimination generalizes) is linear time in the number of input bytes, rather than the number of input records. One special case is when each element has a constant number of bytes, like you mention, but it isn't the only case.
- KirinDave 8y agoCan you name a non-infinite dataset with an unbounded domain? One without a trivial mapping function? Everything we work with is amenable to Radix Sort. This was a big part of Henglein's work.