They probably mean the "postman sort", or whatever catchy name it goes by (radix sort, IIRC). That doesn't involve any comparisons between elements to be sorted. Think of how a postman sorts mail into P.O. boxes... you just algorithmically map a number to a row and column (bin), and deliver. This truly is O(N), but there's a catch: it doesn't work when you don't have bins to sort into, or when you don't know even how many bins you'll need. If you try to generalize this it becomes O(N log N).

Well... Actually. No. First of all, radix sort uses structural features to arrive at linear time, it doesn't incomplrtely sort the input.

Secondly, I've tried to get the white paper exposed here and it generally goes over like a lead balloon but:

http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...

Is the technique. It's an imposing 80 page paper even dedicated educators like Edward Kmett has trouble explaining trivially, but there is a talk here by the author to help sum it up: https://www.youtube.com/watch?v=sz9ZlZIRDAg

We've had some of Henglein's associates here to talk about it, too.

There is a Haskell implementation and it can really speed up certain types of operations. It's tricky to get the constants low in Haskell, but Kmett seems to have done a pretty good job.

Please see my comment below.