# 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[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

```