Я написал эту реализацию алгоритма медианы медиан в Python, но он, похоже, не дает правильного результата, и он также не кажется мне линейной сложностью, есть идеи, где я ушел с пути?

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

Функция называется так:

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

Л.Э .: Извините. GetMed была функцией, которая просто сортировала список и возвращала элемент в len (list), он должен был быть выбран там, я исправил это сейчас, но все же я получаю неправильные результаты. Что касается отступа, код работает без ошибок, и я не вижу в этом ничего плохого: - ??

LE2: Я ожидаю 50 (для текущего L), это дает мне выходы от 30 до 70, не больше, не меньше (пока)

LE3: Большое спасибо, это помогло, теперь это работает. Я путаюсь, хотя, я пытаюсь провести сравнение между этим методом и наивным, где я просто сортирую массив и выводю результаты. Теперь, из того, что я прочитал, временная сложность метода select должна быть O (n)Детерминированный отбор, Хотя я, вероятно, не могу конкурировать с разработчиками Python для оптимизации, я ожидал более близких результатов, чем получил, например, если я изменю диапазон списка на 10000000, select выводит результат за 84.10837116255952 секунд, а метод сортировки и возврата делает это в 18.92556029528825. Какие есть хорошие способы сделать этот алгоритм быстрее?