def select(pos, seq):
    """select(pos, seq): find the nth rank ordered element
    (the least value has rank 0).
    Note1: it modifies the seq.
    Note2: this function is useful with Psyco, otherwise .sort is
    faster until len(seq)>~3e6"""
    # Version 1.1, Nov 13 2004, from "Numerical Recipes".
    lo = 0
    up = len(seq)-1
    if pos<lo or pos>up:
        raise 'Selection out of bounds.'
    else:
        while up>=pos and pos>=lo:
            i = lo
            j = up
            tempr = seq[pos]
            seq[pos] = seq[lo]
            seq[lo] = tempr
            # Split in two
            while i<j:
                while seq[j] > tempr:
                    j -= 1
                seq[i] = seq[j]
                while i<j and seq[i]<=tempr:
                    i += 1
                seq[j] = seq[i]
            seq[i] = tempr
            # Select sub
            if pos<i:
                up = i-1
            else:
                lo = i+1
        return seq[pos]
select(pos, seq): find the nth rank ordered element
    (the least value has rank 0).
    Note1: it modifies the seq.
    Note2: this function is useful with Psyco, otherwise .sort is
    faster until len(seq)>~3e6
recipes/Python/466330_Fast_select/recipe-466330.py