Как объединить отсортированные части файла?

Когда данные слишком велики для оперативной памяти, их сортируют, разбивая на части, сортируя каждую часть в памяти и сохраняя на диск. Финальный этап — объединение этих отсортированных частей в один итоговый файл. Этот процесс называется внешним слиянием (external merge).

Как работает алгоритм слияния

Основная идея — использовать подход, аналогичный слиянию двух отсортированных массивов, но расширить его на K частей. Для этого нужно постоянно знать текущий минимальный элемент среди всех частей.

• Открываем все отсортированные части (файлы) для чтения.
• В памяти создаём структуру (например, массив или кучу), которая хранит по одному текущему элементу из каждой части.
• На каждом шаге находим минимальный элемент среди этих текущих значений.
• Записываем этот минимальный элемент в результирующий файл.
• Сдвигаем указатель в той части, откуда был взят элемент: читаем следующий элемент из этого файла и обновляем структуру в памяти.
• Процесс повторяется, пока все части не будут полностью прочитаны.

Пример реализации на Python

Ниже приведён упрощённый пример слияния нескольких отсортированных файлов чисел, где в памяти хранится лишь по одному числу из каждого файла.

import heapq

def merge_sorted_files(output_path, input_paths):
    # Открываем все входные файлы
    files = [open(path, 'r') for path in input_paths]
    try:
        # Инициализируем кучу (min-heap) первыми числами из каждого файла
        heap = []
        for i, f in enumerate(files):
            line = f.readline().strip()
            if line:  # если файл не пустой
                heapq.heappush(heap, (int(line), i))
        
        # Открываем выходной файл для записи
        with open(output_path, 'w') as out:
            while heap:
                # Извлекаем минимальное число и индекс файла
                value, file_idx = heapq.heappop(heap)
                out.write(str(value) + '\n')
                
                # Читаем следующее число из того же файла
                next_line = files[file_idx].readline().strip()
                if next_line:
                    heapq.heappush(heap, (int(next_line), file_idx))
    finally:
        # Закрываем все открытые файлы
        for f in files:
            f.close()

# Пример использования
if __name__ == '__main__':
    merge_sorted_files('merged.txt', ['part1.txt', 'part2.txt', 'part3.txt'])

В этом примере используется структура данных «куча» (heapq), которая эффективно поддерживает минимум. Для каждого файла мы храним его текущий элемент и индекс, чтобы знать, откуда читать следующее значение.

Где применяется

Такой подход критически важен в системах обработки больших данных (Big Data), в базах данных для сортировки результатов, превышающих память, и в утилитах командной строки, таких как sort в Unix. Он является основой для MapReduce и других распределённых алгоритмов.

Вывод: Алгоритм слияния отсортированных частей файла следует применять, когда необходимо обработать (отсортировать, объединить) набор данных, который не помещается в оперативную память, что типично для логов, дампов БД или результатов распределённых вычислений.