Сложность по времени будет O (n log (n)) независимо от количества процессоров и / или количества внешних накопителей.Общее время будет T (n / a logb (n)), но, поскольку a и b являются константами, сложность времени остается неизменной при O (n log (n)), даже если время, скажем, в 10 раз быстрее.
Мне не понятно, что вы подразумеваете под "параллельной" внешней сортировкой.Я предполагаю несколько ядер или несколько процессоров, но есть ли несколько дисков?Все ли N ядер или процессоров совместно используют одну и ту же память, которая содержит только 1 КБ элементов, или у каждого ядра или процессора есть своя собственная «1 КБ» памяти (фактически имеющая «НК» памяти)?
externalсортировка слиянием в общем
На начальном этапе входной массив читается кусками размера B (1k элементов), сортируется и записывается в K отсортированных файлов.Конечный результат этого начального прохода - K отсортированных файлов размера B (1k элементов).Все остальные проходы будут последовательно объединять отсортированные файлы до тех пор, пока не будет создан один отсортированный файл.
Первоначальный проход обычно связан с процессором, а использование нескольких ядер или процессоров для сортировки каждого куска размера B уменьшит время,Для начального прохода можно использовать любой метод сортировки или любой стабильный метод сортировки.
Для фазы слияния возможность выполнения операций ввода-вывода параллельно с операциями слияния сократит время.Использование многопоточности для перекрытия ввода-вывода с операциями слияния сократит время и будет проще, чем использование асинхронного ввода-вывода для того же.Я не знаю, как использовать многопоточность для сокращения времени операции k-way merge.
Для k-way merge файлы читаются небольшими порциями размера B / (к + 1).Это позволяет использовать k входных буферов и 1 выходной буфер для k-way операции слияния.
Для жестких дисков возникают проблемы с произвольным доступом, скажем, скорость передачи составляет 200 МБ / с, а средняя нагрузка с произвольным доступом равна0,01 секунды, то есть столько же времени для передачи 2 МБ.Если размер буфера составляет 2 МБ, то издержки произвольного доступа эффективно снижают скорость передачи на 1/2 - ~ 100 МБ / с.Если размер буфера составляет 8 КБ, то издержки произвольного доступа эффективно снижают скорость передачи на 1/250 до ~ 0,8 МБ / с.При небольшом буфере двустороннее объединение будет быстрее из-за издержек произвольного доступа.
Для твердотельных накопителей в несерверной установке обычно нет очереди команд, а издержки команд составляют около .0001второй на читает, .000025 второй на пишет.Скорость передачи данных составляет около 500 МБ / с для твердотельных накопителей с интерфейсом Sata.Если размер буфера составляет 2 МБ, накладные расходы команды незначительны.Если размер буфера составляет 4 КБ, то скорость чтения сокращается на 1 / 12,5 до ~ 40 МБ / с, а скорость записи уменьшается на 1 / 3,125 до ~ 160 МБ / с.Поэтому, если размер буфера достаточно мал, повторное двухстороннее объединение будет быстрее.
На ПК эти небольшие сценарии буфера маловероятны.В случае сортировки gnu для больших текстовых файлов с настройками по умолчанию она выделяет чуть более 1 ГБ оперативной памяти, создавая отсортированные файлы объемом 1 ГБ на начальном этапе, и выполняет слияние в 16 направлений, поэтому размер буфера составляет 1 ГБ / 17 ~= 60 МБ.(17 для 16 входных буферов, 1 выходного буфера).
Рассмотрим случай, когда все данные помещаются в память, и что память состоит из k отсортированных списков.Временная сложность для объединения списков будет O (n log (k)), независимо от того, используется ли двухсторонняя сортировка слиянием, объединение пар списков в любом порядке или если для объединения всехсписки за один проход.
Я провел некоторое тестирование этого на моей системе, Intel 3770K 3,5 ГГц, Windows 7 Pro 64 бит.Для k-way слияния на основе кучи, с k = 16, скорость передачи ~ 235 МБ / с, с k = 4, скорость передачи ~ 495 МБ / с.Для 4-стороннего слияния без кучи скорость передачи ~ 1195 МБ / с.Скорость передачи данных на жестком диске обычно составляет от 70 МБ / с до 200 МБ / с.Типичная скорость передачи SSD составляет ~ 500 МБ / с.Дорогие твердотельные накопители серверного типа (SAS или PCIe) - до 2 ГБ / с чтения, ~ 1,2 ГБ / с записи.