Bucket Sort
lRelated to
hashing
lBoth use indexing,
which is O(1), to find ÒbucketÓ
lSuppose the set of
keys to be sorted is known to be limited to a
relatively small integer range, say {0, 1, É,
R-1}.
lCreate an array of
size R of lists, each entry corresponding
to a key value.
lGo through the data
once, putting each element in the
corresponding list.
lConcatenate the
resulting lists.