Казалось бы, стандартная сортировка с восходящим слиянием может использоваться без изменений.
(1024/64) = 16 строк кэша. Предположим, что сортировка слиянием достигла точки, в которой отсортированные пробеги теперь превышают 64 байта. Во время операций слияния будут использоваться 2 строки кэша для 2 сортируемых прогонов, которые будут объединены, и 1 строка кэша для объединенного вывода. Пропуск кэша будет происходить только после чтения или записи каждых 64 байтов.
Сортировка с восходящим слиянием будет генерировать отсортированные прогоны с размерами степеней 2, что может быть немного более удобным для кэша.
Я не уверен, что разрешено в модификации для сортировки слиянием. Использование гибридной вставки sort + merge sort может сократить время сортировки. Позвольте k = # элементам быть отсортированными с помощью сортировки вставкой, чтобы создать отсортированные серии размером k. Простая реализация состоит в том, чтобы определить количество проходов сортировки, необходимое для сортировки слиянием по принципу «снизу вверх»: passcount = ceil (log2 (N)). Если passcount нечетный, используйте k = 32, если passcount четный, используйте k = 64. Это приводит к четному количеству проходов сортировки слиянием, которые могут чередовать направление слияния на каждом проходе слияния, чтобы избежать необходимости копировать данные во время шаг слияния.
Предположим, что алгоритм сортировки слиянием использует 1 временный массив для хранения элементов 2 объединяемых массивов.
Эта часть не совсем понятна. Более эффективно выполнить одноразовое выделение временного массива того же размера, что и сортируемый массив, а затем использовать идентичные индексации для операций слияния. Менее эффективный метод для каждой операции слияния состоит в том, чтобы выделить временный массив того же размера, что и сумма размеров двух отсортированных прогонов, которые должны быть объединены, которые необходимо будет скопировать в (если до слияния) или из (если после слияния) временный массив. Как уже упоминалось, операция слияния может изменить направление слияния на основе прохода слияния снизу вверх или уровня рекурсии сверху вниз, чтобы избежать копирования данных.