Hpw make lists that are easy to sort.

[Terry Reedy]

"Anton Vredegoor" <anton.vredegoor at gmail.com> wrote in message 
news:eueu79$mkd$1 at news5.zwoll1.ov.home.nl...
| Terry Reedy wrote:
|
| > One could generate the items in order in less space by doing, for 
instance,
| > an m-way merge, in which only the lowest member of each of the m 
sublists
| > is present at any one time.  But I don't know if this (which is
| > O(m*n*log(m))) would be any faster (in some Python implementation) for 
any
| > particular values of m and m.
|
| If hashing is O(n+m), it would mean that it would be faster.
|
| I'm not sure if I can agree with your analysis. All information to
| generate the product is already inside the two lists we begin with.
| Doesn't that make the product less complex than a random n*m matrix? Or
| is that what you are saying with O(m*n*log(m)) ?

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.

I don't know how you would sort by hashing.

Terry Jan Reedy