Newsgroups: rec.puzzles
From: hoey@aic.nrl.navy.mil (Dan Hoey)
Date: 1995/07/07
Subject: Re: NEW SORT METHOD!! FAST!!!!!! NEW??

It's worth mentioning that the information-theoretic lower bound is
only _linear_ in the usual metric--the size of the input.  For that
Omega(N log N) is actually the time to sort N items of size log N.
Of course, ordinary radix sort on fixed-length records is also linear
in the size of the input.

A few years back, Dan Bernstein was pushing a form of dynamic radix
sort that (as I recall) is linear in the size of the problem for
variable length records.  He also challenged the theorists to come up
with a sorting problem that could not be recast into a radix sort on
fixed-length records with only linear time costs.  I didn't follow all
the resulting brouhaha, but it at least seems plausible to me.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil