Hpw make lists that are easy to sort.

[Anton Vredegoor]

Terry Reedy wrote:

> If I understand correctly, you want to multiiply each of m numbers by each 
> of n numbers, giving m*n products.  That is O(m*n) work.  Inserting (and 
> extracting) each of these is a constant size m priority cue takes, I 
> believe, O(log(m)) work, for a total of m*n*log(m).  That is faster than 
> O(m*n*log(m*n)) for sorting m*n random numbers.

According to this page:

http://maven.smith.edu/~orourke/TOPP/P41.html

You are very close. The only thing is whether the logarithmic factor can 
be removed.

But there's more:

</quote>
If the input consists of n integers between - M and M, an algorithm of 
Seidel based on fast Fourier transforms runs in O(n + M log M) time 
[Eri99a]. The $ \Omega$(n2) lower bounds require exponentially large 
integers.
<quote>

So maybe there is something at least for this specific case. I hope I'm 
not irritating someone by posting my thought processes here, since 
posting things sometimes seems to be the only way to find the links. I 
wonder if it's the selective attention that makes them turn up after 
posting or whether your talk about big O's has put me on the right track.

Thanks anyway. The problem is still open in general, but some hacks are 
possible, as Paul Rubin said.

A.