What is the best way to merge two lists?

[Delaney, Timothy]

> From: Gonçalo Rodrigues [mailto:op73418 at mail.telepac.pt]
> 
> I believe it has also been made stable-sort. The con is that 
> it gobbles
> up more memory.

Yes, the 2.3 sort is stable, but it has been decided that there will never
be a guarantee that list.sort() will be stable. It's purely an
implementation detail - if an improved, non-stable implementation is
discovered then list.sort() may become non-stable once again.

The stability is purely a side effect of the algorithm used, which is faster
in all cases that Tim Peters tested (he thought of a lot of nasty cases)
than the current implementation (*much* faster in many cases). I wouldn't
use the term "gobbles" up more memory - it uses a *little* bit more memory.
"Gobbles" implies that it uses a *lot* more memory.

In any case, the DSU pattern to maintain stability is still useful, even if
you rely on the stability of the algorithm. Performance has shown to be much
better using indexed DSU than simply relying on the stable algorithm.

Tim Delaney