Recursive functions for sorting
I recommend you be more consistent in not combining if followed by a statement sequence ending in return with an else (I left out the comments):

def separate(p,l):
    if len(l) == 0:
        return ([],[])
    (true_list, false_list) = separate(p,l[1:])
    if p(l[0]):
        return ([l[0]] + true_list, false_list)
    return (true_list, [l[0]] + false_list)


as you do e.g. in compare().

In compare() I would nest the conditions (arbitrarily based on a):

def compare(a,b):
    if a == '':
        if b == '':
            return '='
        return '&lt;'
    if a != '':
        if b == '':
            return '&gt;'
    if a[0] &gt; b[0]:
        return '&gt;'
    if a[0] &lt; b[0]:
        return '&lt;'
    return compare(a[1:],b[1:])


That way it is more clear to me that compare() never ends without a return value.

Your comments should at least use triple double quotes (PEP8) and you should try to conform to PEP 257 (docstring conventions).