What is the best way to merge two lists?

[John Hunter]

>>>>> "Pierre" == Pierre Rouleau <pieroul at attglobal.net> writes:

    >> However, the builtin sort is not stable,
    Pierre> In what sense?

A stable sort is one in which 2 elements that compare equal have their
relative order preserved in the sorted and unsorted sequence.  For
objects like numbers, strings and lists, this doesn't matter, because
a 1 is a 1 is a 1.  Integers which compare the same in python *are the
same*.

But since python allows you to define your own comparison functions,
two objects that compare equal may not be the same.  This becomes
especially prominent for user defined classes with many attributes,
where there are many possible sort criteria.  The built-in list sort
does not guarantee anything about the relative order of these objects
in the sorted list, and hence is not 'stable' and not deterministic in
the sense you want.

Suppose you have a class StockQuote, which has attributes price, time,
ticker, volume.  You can write a custom comparison function to sort a
list of stock quotes, that says 

  quote1<quote2 iff quote1.price<quote2.price

If you sort the list, the quotes will be arranged by price, but there
could be many quotes at the same price in your list which are
fundamentally different objects (eg they occurred at different times).
A stable sort guarantees that the relative order of these quotes will
be unchanged in the sort.

The DSU pattern I refereed to above is one of the techniques people
use to take advantage of python's built-in sort efficiency while
guaranteeing a stable sort.

Incidentally, the efficiency of sort in the yet-to-be-released
python2.3 is rumored to be substantially improved.

John Hunter