Какие существуют подходы к внешней сортировке данных?

Некоторые подходы к внешней сортировке данных:

• Внешняя сортировка слиянием. 2 Обычно использует гибридную стратегию сортировки-слияния. 2 На этапе сортировки считываются, сортируются и записываются во временный файл фрагменты данных, достаточно маленькие, чтобы поместиться в основной памяти. 2 На этапе объединения отсортированные вложенные файлы объединяются в один файл большего размера. 2
• Сортировка по распределению. 2 Напоминает быструю сортировку. 2 Алгоритм находит поворотные элементы и использует их для разделения данных на подмассивы примерно одинакового размера, каждый из которых меньше следующего. 2 Затем выполняет рекурсию до тех пор, пока размеры подмассивов не станут меньше размера блока. 2
• Внешняя поразрядная сортировка. 3 Это метод, который не основан на процедуре слияния. 3 Его иногда называют распределяющей сортировкой, поколонной сортировкой, карманной сортировкой, цифровой сортировкой, сортировкой разделением и т. д.. 3

Также к основным методам внешней сортировки относятся алгоритм прямого слияния, алгоритм естественного слияния, многопутевое слияние и многофазная сортировка. 1