JB wrote:
        ...
>  bigger. I thought that when f is slow, then at least the
>  merging should be as fast as possible.

Wrong attitude.  If f is slow enough, all that matters is
minimizing the numbers of calls to f -- everything else
is secondary and might as well be optimized for clarity
and simplicity instead.


>  I thought that as have many entries, O(n) should mean "as
>  fast as possible".

As N goes to infinity, yes.  For real cases, maybe, and maybe
not.  If f(x) selects few enough x's, my first suggestion may
be generally preferable -- even though its WORST CASE
(that's what big-O notation is generally about...!) is O(N log N)
rather than O(N).  How often is the worst case encountered,
and what are the multiplicative constants in play...?


Alex

-- 
http://mail.python.org/mailman/listinfo/python-list