Поиск индекса элемента, который будет вставлен в большой отсортированный набор - проблемы с памятью в bisect?

Question

Учитывая большой отсортированный список l размера n и элемент x, я хочу найти индекс x, если он должен быть вставлен в l.

Очевидный способ сделать это - разделить пополам:

def bis(l, x):
    m = len(l)
    if m <= 1:
        return m
    elif l[m//2] < x:
        return m//2+bis(l[m//2:], x)
    else:
        return bis(l[0:m//2], x)

Это похоже на реализацию метода bisect.bisect и должно выполняться в $ O (\ log n) $.

Однако, когда списки становятся большими, обработка разделенных пополам списков занимает вечность, и код выполняется приблизительно линейно.

Есть ли способ избежать этого?