Implementación en Python del algoritmo “mediana de medianas”

He escrito esta implementación del algoritmo de la mediana de las medianas en python, pero no parece dar el resultado correcto, y tampoco me parece de complejidad lineal, ¿alguna idea de dónde salí del camino?

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

La función se llama así:

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

LE: Lo siento. GetMed fue una función que simplemente clasificó la lista y devolvió el elemento a len (lista), debería haber sido seleccionado allí, lo arreglé ahora, pero aún así obtengo los resultados incorrectos. En cuanto a la sangría, el código funciona sin errores, y no veo nada de malo en ello: - ??

LE2: Espero 50 (para la L actual), me da salidas de 30 a 70, ni más ni menos (todavía)

LE3: Muchas gracias, hizo el truco ahora funciona. Sin embargo, estoy confundido, estoy tratando de hacer una comparación entre este método y el ingenuo, donde simplemente ordeno la matriz y doy los resultados. Ahora, por lo que he leído hasta ahora, la complejidad temporal del método de selección debe ser O (n)Selección determinista. Aunque probablemente no pueda competir con la optimización que hicieron los desarrolladores de python, esperaba resultados más cercanos de los que obtuve, por ejemplo, si cambio el rango de la lista a 10000000, select produce el resultado en 84.10837116255952 segundos mientras el método de clasificación y retorno Lo hace en 18.92556029528825. ¿Cuáles son algunas buenas maneras de hacer este algoritmo más rápido?

Respuestas a la pregunta(2)

Su respuesta a la pregunta