Hpw make lists that are easy to sort.
Terry Reedy
tjreedy at udel.edu
Thu Mar 29 00:37:09 CEST 2007
"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[m1]*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 mway 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
More information about the Pythonlist
mailing list