Существуют переупорядоченные массивы в соответствии с алгоритмами отсортированного индекса, но они включают произвольный доступ.Даже в случае SSD, хотя сам произвольный доступ не является проблемой, чтение или запись одной записи за один раз из-за произвольного доступа имеет более низкую пропускную способность, чем чтение или запись нескольких записей за один раз, которые обычно отключаются внешнимсортировка слиянием.
Для типичной внешней сортировки слиянием файл читается в «кусках», достаточно маленьких для внутренней сортировки, чтобы отсортировать «порцию» и записать отсортированные «порции» на внешний носитель.После этого начального прохода выполняется «слияние по k» для «чанков», умножая размер слитых «чанков» на k на каждом проходе слияния, пока не будет получен один отсортированный «чанк».Операции чтения / записи могут считывать несколько записей одновременно.Скажем, у вас есть 1 ГБ оперативной памяти и используйте 16-полосное слияниеДля 16-канального слияния используются 16 «входных» буферов и 1 «выходной» буфер, поэтому размер буфера может составлять 63 МБ (1 ГБ / 17 округляется в меньшую сторону для переменного пространства), что позволит читать или записывать 3150 записей навремя, значительно сокращая произвольный доступ и командные издержки.Предполагая, что при первом проходе создаются отсортированные чанки размером 0,5 ГБ, после 3 (16-полосных) проходов слияния размер чанка составляет 2 ТБ, после 4-х проходов - 32 ТБ и т. Д.