Moving list entries from one list to another

[Alex Martelli]

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