Внешняя сортировка слиянием. Сортировка сериями.
Определения
Алгоритм внешней сортировки слиянием, также известный как сортировка сериями, используется для сортировки больших наборов данных, которые не помещаются полностью в оперативной памяти компьютера и должны быть обработаны с использованием внешней памяти, такой как диск.
Основная идея внешней сортировки слиянием заключается в разделении исходного набора данных на небольшие блоки, которые могут быть обработаны в оперативной памяти, и последующем слиянии этих блоков в отсортированный порядок, используя внешнюю память (например, жесткий диск).
- Разделение на серии - исходный набор данных разбивается на несколько блоков, называемых сериями, которые могут быть обработаны в оперативной памяти.
- Внутренняя сортировка серий - каждая серия сортируется внутренним алгоритмом сортировки, таким как сортировка вставками или сортировка слиянием. Это позволяет установить частичный порядок внутри каждой серии.
- Слияние серий - отсортированные серии сливаются в более крупные блоки, сохраняя отсортированный порядок. Этот процесс продолжается до тех пор, пока все серии не будут объединены в один отсортированный набор данных.
- Повторение слияний при необходимости - если в результате слияния формируется более крупная серия, чем может быть обработано в оперативной памяти, эта серия разбивается на более мелкие серии, которые затем сортируются и сливаются с другими сериями.
Пример
Предположим, у нас есть большой файл с данными, который не может быть загружен полностью в оперативную память компьютера. Мы хотим отсортировать этот файл.
- Разделение на серии - файл разбивается на несколько блоков, каждый из которых может быть обработан в оперативной памяти. Размер блоков определяется доступной оперативной памятью.
- Внутренняя сортировка серий - каждый блок считывается в память, и внутренним алгоритмом сортировки, например, сортировкой слиянием, отсортированы его элементы.
- Слияние серий - отсортированные блоки сливаются попарно в большие отсортированные блоки, сохраняя отсортированный порядок.
- Повторение слияний при необходимости - если после слияния размер полученной серии превышает доступную оперативную память, серия разбивается на более мелкие блоки, которые сортируются и сливаются с другими сериями.