Как объединить два отсортированных файла в один отсортированный при ограничении памяти

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

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

Как отвечать

Идея: слияние двумя указателями, как шаг merge sort. В каждый момент в памяти по одной текущей строке из каждого файла; пишется меньшая, читается следующая из того же файла. Время O(n + m), дополнительная память O(1) с точностью до буферов ввода-вывода.

В Python цикл руками писать не обязательно. Откройте оба входных файла и выходной в одном with, дальше одна строка: out.writelines(heapq.merge(fa, fb)). Файловый объект итерируется лениво, по строке, и heapq.merge тоже ленивый генератор, так что в памяти ничего не копится. Для равных элементов он берёт сначала из первого источника, то есть слияние устойчивое. Если строки нужно сравнивать как числа, передайте key=int или функцию, которая разбирает нужное поле.

Дальше покажите, что видите края:

• перевод строки: если последняя строка файла без \n, она склеится со следующей. Нормализуйте концы строк;
• порядок сравнения: строки сравниваются лексикографически, "10" < "9". Компаратор слияния должен совпадать с тем, которым файлы сортировали;
• кодировка: укажите encoding="utf-8" явно, не полагаясь на системную;
• k файлов: тот же heapq.merge(*files), куча размером k, время O(N log k);
• неотсортированные данные: внешняя сортировка. Режем на куски, которые влезают в память, сортируем каждый, пишем во временные файлы и сливаем k-путевым слиянием.

В Unix то же самое делает sort -m a.txt b.txt, это хорошая реплика в конце.

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

Читают файлы через read() или readlines(). Это сразу проваливает условие про ограничение памяти.

Забывают про последнюю строку без перевода строки и получают склеенные записи на стыке файлов.

Сравнивают числа как строки или сливают файлы, отсортированные по другому правилу. Результат выглядит правдоподобно, но порядок в нём неверный.