Surprising (for me) benchmark results...

[Darren New]

> > There are O(N) sorting algorithms??  I thought that was restricted to
> > quantum computation.
> 
> Actually, there are O(N) sorting algorithms. Counting sort is O(N). 

The right answer is that the best sorting algorithm you can get is O(N lg N)
if you're restricted to simply comparing two values without looking inside.
If you know something about the internal structure of the data you're
sorting (like, it's integers, or you can look at individual characters of
the strings you're sorting) you can get faster performance.

This is classical computing, not quantum computing. I'll catch up on quantum
computing when I can buy a board that plugs into a PCI slot with a quantum
processor on it. ;-)

-- 
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
       San Diego, CA, USA (PST).  Cryptokeys on demand.
       Invasion in chinese restaurant:
                        ALL YOUR RICE ARE BELONG TO US!