Hpw make lists that are easy to sort.

[Paul Rubin]

Anton Vredegoor <anton.vredegoor at gmail.com> writes:
> Presorting the second sequence gains us more than three seconds. I
> wonder if there is a way to generate the combined items in such a way
> that sorting them is even faster? Is there some other sorting
> algorithm that can specifically take advantage of this way -or another
> way- of generating this list?

Well there are various hacks one can think of, but is there an actual
application you have in mind?

> The final sequence is len(L)*len(R) long but it is produced from only
> len(L)+len(R) different items, is it possible to exploit this fact?
> I'd also be interested in a more general solution that would work for
> summing the items of more than two lists in this way.

If you really want the sum of several probability distriutions (in
this case it's the sum of several copies of the uniform distribution),
it's the convolution of the distributions being summed.  You can do
that with the fast fourier transform much more efficiently than
grinding out that cartesian product.  But I don't know if that's
anything like what you're trying to do.