Можно ли добавить проверку сортировки входных списков для защиты от некорректных данных?

Что проверяют

Обычно это продолжение задачи на отсортированные входы: слияние, пересечение, бинарный поиск. Интервьюер смотрит, понимаете ли вы цену проверки относительно самого алгоритма и где её разумно ставить. Следом спрашивают, что делать, если список всё же не отсортирован.

Как отвечать

Да, и проверка простая: один линейный проход с попарным сравнением соседей.

from itertools import pairwise

def is_sorted(xs):
    return all(a <= b for a, b in pairwise(xs))

itertools.pairwise есть с Python 3.10, в NumPy то же делает np.all(np.diff(a) >= 0), в pandas есть Series.is_monotonic_increasing. Важнее решения вокруг этой строки:

• цена: проверка стоит O(n). Для слияния за O(n + m) это приемлемо, асимптотика не меняется. Для бинарного поиска за O(log n) проверка на каждом вызове уничтожает весь смысл, её ставят один раз на входе в систему;
• без лишнего прохода: при слиянии можно помнить предыдущий элемент каждого списка и падать, как только встретили убывание;
• реакция: упасть с ValueError и понятным сообщением или отсортировать самим за O(n log n). Это вопрос контракта функции, его стоит проговорить вслух;
• assert против исключения: assert исчезает при запуске с python -O, для проверки входных данных он не годится.

В пайплайне данных такая проверка обычно живёт не внутри функции, а в валидации на границе: схема в pandera или ожидания в Great Expectations, с отчётом, какая партия пришла битой.

Где спотыкаются

Забывают про NaN. Любое сравнение с ним ложно, поэтому проверка вида «ищем a[i] > a[i+1]» пропустит список с NaN как отсортированный.

Не уточняют, нужна строгая сортировка или нет. Для пересечения множеств дубликаты могут быть ошибкой данных, а <= их пропустит.

Вставляют проверку в горячую функцию, которую миллион раз зовут на одном и том же списке, и превращают логарифмический алгоритм в линейный.