What is the best way to merge two lists?

[John Hunter]

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

    Pierre> Is there a more efficient way to merge heterogenous lists
    Pierre> than the brute force approach used by uniq() above?

Your question really boils down to getting unique items from a list,
stably.  You can always just concatenate your two lists and then
unique them, so the merge question is secondary.

Take a look at Tim Peter's recipe at
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560.

His approach is to try alternate methods in order of decreasing
efficiency, moving to the next if the previous fails.  I think his
sort based approach for non-hashable elements will offer improved
performance over your brute force approach.

However, the builtin sort is not stable, so I don't think it will meet
your criterion of deterministic output.  But there is a fair amount of
discussion on that page about the best way to get uniqueness in the
presence of possibly unhashable elements, and various approaches for
dealing with stability -- see Alex's comments after the recipe.

Search google groups for 

  dsu group:*python*

DSU (Decorate Sort Undecorate) is a common idiom for handling sorts
when you are worried about stability.  Also, there is a nice,
informative chapter in The Python Cookbook devoted to the subject,
which basically focuses on the DSU approach.

JDH