Moving list entries from one list to another

[JB]

I have two lists <list1> and <list2>. The entries of these 
lists have the format (id,rest), where <id> is a natural 
number. The list are sorted, the key is <id>. 
I should like to write a funtion move:

def move(f):

The argument <f> is a predicate: 
  f: {set of entries of list1} --> {true, false}
Now all elements of list1, for which <f> returns true, 
should be moved to list2. It is very important, that 
<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)?

TIA,
-- 
Janos Blazi


-----------== Posted via Newsfeed.Com - Uncensored Usenet News ==----------
   http://www.newsfeed.com       The #1 Newsgroup Service in the World!
-----= Over 100,000 Newsgroups - Unlimited Fast Downloads - 19 Servers =-----