"Anton Vredegoor" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] | 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 -- http://mail.python.org/mailman/listinfo/python-list
