Entry

How is it possible to sort n elements faster than n(log n)?

Jan 3rd, 2005 13:11
Ken Bateman, Martin Blomberg,

n(log n) is the fastest way to sort n elements. Some people say that,
using antother approach, e.g. radix sort or distribution sort, you can
actually sort the elements in linear time.  I believe they are wrong.

These people say that a radix sort on N elements completes in time
proportional to N, aka "in linear time".  Actually, a radix sort
completes in time proportional to N(log k) where k is the number of
possible values the key field can contain.  When k < N, you're not
actually sorting, instead you are partitioning the N elements into k
bins.  So, in order for a radix sort meaningfully be a sort (and not a
partitioning) you must have k >= N.  So, a radix sort takes time N(log
k), and k >= N, so a radix sort is, at best, as fast as a typical N(log
N) sort, and at worst, slower than N(log N).

For example, think of a radix sort done with 16 bins (4-bit radix) and a
32-bit key.  During the execution of this radix sort, 8 passes over the
data are required.  When N is small (say, N=25), 8 passes is typically
much larger than the (log N) term would be in a more typical comparison
sort.  You should not expect a radix sort to be competitive in speed to
a comparison sort unless N is very close to k.