Hpw make lists that are easy to sort.

[Terry Reedy]

"Anton Vredegoor" <anton.vredegoor at gmail.com> wrote in message 
news:euenlj$oll$1 at news4.zwoll1.ov.home.nl...
| Paul Rubin wrote:
|
| > Well there are various hacks one can think of, but is there an actual
| > application you have in mind?
|
| Suppose both input lists are sorted. Then the product list is still not
|  sorted but it's also not completely unsorted. How can I sort the
| product? I want to know if it is necessary to compute the complete
| product list first in order to sort it. Is it possible to generate the
| items in sorted order using only a small stack?

If you have lists A and B of lengths m and n, m < n, and catenate the m 
product lists A[0]*B, A[1]*B, ..., A[m-1]*B, then list.sort will definitely 
take advantage of the initial order in each of the m sublists and will be 
faster than sorting m*n scrambled items (which latter is O(m*n*log(m*n))).

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.

Terry Jan Reedy