JB wrote:
        ...

>  <list2> remains sorted, that is, the entries from <list1>
>  should be inserted to the right positions in <list2>. When
>  <n> is defined by
>  n := max(len(list1),len(list2)),
>  then <move> should work in O(n) time.
>  
>  Any hints of how to do this (as fast as possible)?

Hmmm, I hadn't seen the O(N) constraint.  The approach
previously posted by Emile and commented on by me does
not guarantee meeting that constraint: it CAN happen to
become O(N log N) when most of list2 ends up appended
to list1.  For an O(N) guarantee, I think you must use 
a merge-like linear scan on the lists -- also requiring
O(N) temporary auxiliary storage, of course.


Here's a fancifully-expressed solution...:

au = [None] * 2
it = iter(list1)
au[0] = [ it.next(), 0, it, [] ]
it = iter(list2)
au[1] = [ it.next(), 1, it, [] ]

while True:
    m = min(au)
    i = m[1]
    if i and f(m[0]): i = 0
    au[i][3].append(m[0])
    try: m[0] = m[2].next()
    except StopIteration: break

# now, either list is exhausted
# if any tail is left in the first list, copy it
au[0][3].extend(au[0][2])
# if any tail is left in the second list, distribute it
for x in au[1][2]:
    au[not f(x)][3].append(x)

# finally, copy the results back
list1[:] = au[0][3]
list2[:] = au[1][3]


OK, OK, NOT the most lucid code I ever posted, I agree.

But I get it by reasoning back from the GENERAL case of
mergesort (for any number of streams) and specializing
for 2 streams AND adding the subtle asymmetry beteween
the first list (whose items must all go to the first
auxiliary list) and the second one (whose item must go
to the first auxiliary list iff they satisfy predicate
f, otherwise to the second auxiliary list).  I bet you
can do better by exploiting the specifics of this case!-)

Still -- this IS O(N) in time and space!


Alex

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