3 ms·
> generalized sorting is O(n) What do you mean by generalized sorting and how isn't this affected by the comparison sorting lower bound? Do you have a source?
by tyilo 9y ago
> generalized sorting is O(n)
What do you mean by generalized sorting and how isn't this affected by the comparison sorting lower bound?
Do you have a source?
- cryptonector 9y agoThey 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).
- KirinDave 9y agoWell... 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/henglein2011a.pdf 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 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.
- deleted 9y ago[deleted]
- KirinDave 9y agoPlease see my comment below.