> 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.