Eu escrevi essa implementação do algoritmo mediano de medianas em python, mas não parece produzir o resultado certo, e também não parece ser uma complexidade linear para mim, alguma idéia de onde eu saí da pista?

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
    Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

A função é chamada assim:

L = list(range(100))
shuffle(L)
print(select(L))

LE: Desculpe. GetMed era uma função que simplesmente classificava a lista e retornava o elemento em len (lista), deveria ter sido selecionado lá, eu o consertei agora, mas ainda assim recebo as saídas erradas. Quanto ao recuo, o código funciona sem erro, e não vejo nada de errado com isso: - ??

LE2: Estou esperando 50 (para o atual L), me dá saídas de 30 a 70, nem mais nem menos (ainda)

LE3: Muito obrigado, o truque funcionou agora. Porém, estou confuso, estou tentando fazer uma comparação entre esse método e o ingênuo, onde eu simplesmente classifico a matriz e envio os resultados. Agora, pelo que li até agora, a complexidade de tempo do método select deve ser O (n)Seleção Determinista. Embora eu provavelmente não possa competir com a otimização que os desenvolvedores python fizeram, esperava resultados mais próximos do que consegui, por exemplo, se eu alterar o intervalo da lista para 10000000, selecione as saídas como resultado em 84.10837116255952 segundos enquanto o método de classificação e retorno faz isso em 18.92556029528825. Quais são algumas boas maneiras de tornar esse algoritmo mais rápido?