Как вставить элемент в отсортированный список так, чтобы он остался отсортированным?

Для отсортированного списка есть модуль bisect — он находит позицию бинарным поиском за O(log n):

import bisect
lst = [1, 3, 5, 7]
bisect.insort(lst, 4)
print(lst)  # [1, 3, 4, 5, 7]

insort сам найдёт место и вставит. Важно: сама вставка в список всё равно O(n) (надо сдвинуть хвост), но поиск позиции — логарифмический, что заметно быстрее линейного прохода. Если же список не отсортирован, bisect даст неверный результат — он рассчитан только на упорядоченные данные.