Fast select (Python recipe) by bearophile -

ActiveState Code (http://code.activestate.com/recipes/466330/)

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]


try: # Import Psyco if available.
# Psyco is almost necessary, otherwise .sort is faster until len(seq)>~3e6
    import psyco
except ImportError:
    pass
else:
    psyco.bind(select)


if __name__ == '__main__': # Test ----------------------
    from time import clock
    import random
    nrepetiotions = 6
    print "nrepetiotions=", nrepetiotions
    print "len(list), average min time select of 1"\
          "element of list, min time select(list):"
    for j in xrange(6, 21):
        n = 2**j
        v = []
        for i in range(nrepetiotions):
            seq = [random.random() for x in xrange(n+1)]
            nd2 = int(n//2)
            t1 = clock()
            select(nd2, seq)
            t2 = clock()
            v.append(t2-t1)
        print "2^"+str(j)+"=", n, round(1000000*min(v)/n, 3), round(min(v), 3)