Newsgroups: comp.lang.misc
Path: utzoo!utgpu!watserv1!maytag!watdragon!abrodnik
From: abrodnik@watdragon.waterloo.edu (Andrej Brodnik (Andy))
Subject: Re: Sorting bounds
Message-ID: <1990Nov22.142850.19676@watdragon.waterloo.edu>
Keywords: sorting, AKS
Organization: University of Waterloo
References: <1990Nov20.202143.10746@craycos.com>
Date: Thu, 22 Nov 90 14:28:50 GMT
Lines: 17

In article <1990Nov20.202143.10746@craycos.com> jrbd@craycos.com (James Davies) writes:
>The bound on sorting is O(N log N) comparisons because you must be able to
>generate all of the N! possible permutations of the N inputs. ... 
>
>... The log term may be hidden in the addressing hardware of 
>your memory, and may be hidden further by parallelism, but it's there.  

Well in a prallel version of sorting described by AKS in early 80th they took
away the linear part and got O(logN) parallel time algorithm. But the problem
in theis construction is an enormous constant hidden in big O. It originates
from the construction of expander graphs. But I belive that the algorithm was
already described in this discussion.

Regards

Andrej