Сколько циклов нужно для сортировки и объединения списков без лямбда-функций

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

Задача на аккуратность, а не на алгоритмическую эрудицию. Хотят увидеть, что вы не пишете вложенные циклы там, где хватает одного прохода, оцениваете сложность и знаете, чем заменить лямбду в параметре сортировки.

Как отвечать

Разложите на два шага. Слияние двух уже отсортированных списков это один цикл и линейная сложность:

def merge(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

Один while плюс два хвостовых копирования, то есть O(n + m). Если списки не отсортированы, дешевле склеить и отсортировать один раз: sorted(a + b) даёт O(k log k) против двух отдельных сортировок с последующим слиянием.

Запрет на лямбды касается только ключа сортировки, и замена штатная: operator.itemgetter(1), operator.attrgetter или functools.cmp_to_key для попарного сравнения. Добавьте, что sorted устойчив, поэтому сортировка по нескольким полям делается проходами от младшего ключа к старшему, а heapq.merge лениво сливает любое число отсортированных источников, что важно, когда данные не помещаются в память.

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

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

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

Третье: понимают «сколько циклов» буквально и начинают считать итерации на трёх элементах. От вас ждут оценку в O-нотации со словами про худший и средний случай, а не арифметику по конкретному входу, из которой ничего не следует.