What is the best way to merge two lists?

[Gonçalo Rodrigues]

On Sun, 17 Nov 2002 15:09:25 -0600, John Hunter
<jdhunter at nitace.bsd.uchicago.edu> wrote:

>>>>>> "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.

I believe it has also been made stable-sort. The con is that it gobbles
up more memory.

>
>John Hunter

All the best,
G. Rodrigues