Внешняя Сортировка СлияниемExternal Merge Sort

Алгоритм состоит из двух фаз. Фаза 1 (создание отсортированных прогонов): данные читаются последовательными блоками ровно такого размера, чтобы поместиться в доступную память (M), каждый блок сортируется в памяти любым алгоритмом из 2.2.1 (обычно quicksort или merge sort) и записывается обратно на диск как отдельный отсортированный "прогон" (run). Фаза 2 (k-путевое слияние): k отсортированных прогонов сливаются за один проход — в памяти держится только текущий "верх" каждого прогона (k чисел) плюс минимальная структура (обычно min-heap размера k) для быстрого выбора наименьшего среди них; каждый раз, когда элемент выбирается и записывается в результат, из соответствующего прогона на диске подгружается следующий элемент. Инвариант: в памяти в любой момент — не весь массив, а лишь O(k) элементов плюс буферы ввода-вывода, независимо от общего размера данных n.The algorithm has two phases. Phase 1 (creating sorted runs): data is read in sequential blocks sized exactly to fit available memory (M), each block is sorted in memory with any algorithm from 2.2.1 (usually quicksort or merge sort) and written back to disk as a separate sorted "run." Phase 2 (k-way merge): k sorted runs are merged in a single pass — memory holds only the current "top" of each run (k numbers) plus a small structure (usually a min-heap of size k) for quickly picking the smallest among them; every time an element is picked and written to the output, the next element from that run is loaded from disk. Invariant: at any moment, memory holds not the whole array but only O(k) elements plus I/O buffers, regardless of the total data size n.

// упрощённая схема; на практике добавляется буферизация чтения/записи// simplified scheme; real implementations add read/write buffering
std::vector<std::string> create_sorted_runs(std::istream& input, size_t memory_limit) {
    std::vector<std::string> run_files;
    while (auto block = read_block(input, memory_limit)) {
        std::sort(block->begin(), block->end());       // любой in-memory алгоритм из 2.2.1// any in-memory algorithm from 2.2.1
        run_files.push_back(write_to_disk(*block));
    }
    return run_files;
}

void k_way_merge(const std::vector<std::string>& run_files, std::ostream& output) {
    auto cmp = [](const auto& a, const auto& b) { return a.value > b.value; };
    std::priority_queue<RunHead, std::vector<RunHead>, decltype(cmp)> heap(cmp);
    for (auto& f : run_files) heap.push(read_first(f));    // в памяти — только k "голов"// memory holds only the k "heads"
    while (!heap.empty()) {
        auto top = heap.top(); heap.pop();
        output << top.value;
        if (auto next = read_next(top.run_id)) heap.push(*next);
    }
}

"Диск" — общий массив данных, разбитый на прогоны заданного размера (симулирует ограниченную память). Фаза 1 сортирует каждый прогон отдельно; фаза 2 сливает их, показывая только "головы" прогонов, которые реально были бы в памяти — остальные элементы каждого прогона "лежат на диске" (затемнены) до своей очереди.The "disk" is the shared data array, split into runs of a set size (simulating limited memory). Phase 1 sorts each run separately; phase 2 merges them, showing only the runs' "heads" — the elements that would actually be in memory — while the rest of each run "sits on disk" (dimmed) until its turn.

Пусть N — общий размер данных, M — размер доступной памяти, B — размер блока диска за одну операцию чтения/записи. Фаза 1 создаёт N/M прогонов, каждый читается и пишется целиком — O(N/B) операций ввода-вывода. Фаза 2 сливает все прогоны за один линейный проход (если их число k = N/M не превышает M/B — иначе нужно несколько раундов слияния меньшими группами) — ещё O(N/B) операций. Итого O(N/B) операций ввода-вывода при однопроходном слиянии — принципиально другая мера, чем O(n log n) сравнений: она игнорирует все сравнения внутри одного блока памяти (они "бесплатны" по сравнению со стоимостью обращения к диску) и считает только пересечения границы память-диск.Let N be the total data size, M the available memory size, B the disk block size per read/write operation. Phase 1 creates N/M runs, each read and written in full — O(N/B) I/O operations. Phase 2 merges all runs in a single linear pass (if their count k = N/M doesn't exceed M/B — otherwise several rounds of merging smaller groups are needed) — another O(N/B) operations. Total: O(N/B) I/O operations for a single-pass merge — a fundamentally different measure than O(n log n) comparisons: it ignores every comparison inside one memory block (they're "free" compared to the cost of a disk access) and counts only crossings of the memory-disk boundary.

Если k (число прогонов) превышает то, что можно слить за один проход при доступной памяти, слияние проводится в несколько раундов (слить первые m прогонов в один, затем следующие m, и так далее, затем повторить) — это и есть многопроходная внешняя сортировка, дающая O((N/B)·log_{M/B}(N/B)) операций ввода-вывода в общем случае, где логарифм берётся по основанию M/B, а не 2 — куда более благоприятное основание, потому что M/B на практике может быть тысячами (типичный размер памяти в гигабайтах при блоке в килобайты).If k (the number of runs) exceeds what can be merged in one pass given available memory, merging happens in several rounds (merge the first m runs into one, then the next m, and so on, then repeat) — this is multi-pass external sorting, giving O((N/B)·log_{M/B}(N/B)) I/O operations in the general case, where the logarithm's base is M/B, not 2 — a much more favorable base, because M/B can be in the thousands in practice (a typical memory size in gigabytes against a block size in kilobytes).