Surprising (for me) benchmark results...

[Daniel Berlin]

On Thu, 3 May 2001, John J. Lee wrote:

>
> [I wrote]
> > There are O(N) sorting algorithms??  I thought that was restricted to
> > quantum computation.
> [...]
>
> Actually, there is no quantum algorithm that works better than O(N ln N)
> either.  There is a *search* that is better than the classical limit.

Not yet, anyway.It's provable that you can't do comparison based sorting
in less  time than O(N ln N), unless you can make  N log N comparisons take less than N
Log N time (IE less than O(1) per comparison).
You might actually be able to pull off the < O(1) per comparison on a
quantum computer by finding some way to evaluate more than one comparison at a time, and have it take
the same time as just one (You can already do this type of thing if you
have multiple CPU's.)
--Dan