Sort one sequence by O(n) in time and O(1) in space

[Tim Daneliuk]

On 02/10/2014 04:20 AM, Sturla Molden wrote:
> In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
> bound on the complexity.

Only true for sorting that involve comparison.  However, sorts that use
the values of the inputs as positional keys have a lower bound
complexity (omega) of O(n) and a worst case complexity of O(n)
and are thus asymptotically optimal.

For example, given a range of integers guaranteed to be within
the range of j to k (lower to higher), one can created a bit field
to represent all possible values of j to k.  Then, as values are
read in, the corresponding but is set true.  You have to process
the list of n elements once to read it in, and then a second
time to read them out in order.  This is a 2n operation which is O(n).

For very large ranges of j to k, this is impractical and we resort
to things like hashing functions which can perform better than
n log n sorting algorithms.  But there are lots of real world
applications where inputs-as-keys works just fine, such as short
dispatch tables in operating systems where the value to be
sorted represents a process priority, for example.

-- 
----------------------------------------------------------------------------
Tim Daneliuk     tundra at tundraware.com
PGP Key:         http://www.tundraware.com/PGP/