На этом шаге мы приведем классификацию методов сортировки.
Традиционно методы сортировки делят на внутренние и внешние [1, с.10].
Внутренние методы - это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной (оперативной) памяти процессора.
Слово список часто обозначает набор записей, расположенных в основной памяти.
Внешние методы - это такие методы, которые приемлемы для файлов данных, которые слишком велики, чтобы поместиться в основной памяти, и поэтому должны в течение процесса сортировки располагаться на устройствах внешней памяти (лентах, дисках, барабанах).
В процессе внешней сортировки часть файла считывается в основную память, там упорядочивается, а затем переписывается на внешние устройства. Этот процесс повторяется несколько раз. Внутренние методы используются для перестановки данных, обрабатываемых между пересылками. Поэтому, когда говорят о сортировке на ленте, то подразумевают не только процесс считывания и записи на эти ленты, но также и внутреннюю сортировку, которая упорядочивает и комбинирует элементы с этих лент по мере их считывания.
(1) Лоpин Г. Соpтиpовка и системы соpтиpовки. - М.: Hаука, 1983. - 384 с.
На следующем шаге мы рассмотрим несколько алгоритмов внутренней сортировки.
