Краткие теоретические сведения. Под сортировкой понимают процесс переупорядочивания некоторого множества объектов с целью их размещения в заданном порядке

Под сортировкой понимают процесс переупорядочивания некоторого множества объектов с целью их размещения в заданном порядке. Это универсальный вид деятельности с точки зрения обработки данных, которые представляют собой последовательность ключей. С помощью сортировки добиваются такого их размещения, чтобы было выполнено условие:

f(a[1]) f(a[2])f(a[3])… f(a[N]),

где символ означает знак предшествования, а f -некоторая функция упорядочивания. При упорядочивании по возрастанию, после сортировки будет выполнено условие:

a[1] a[2] a[3] ... a[N]

В ходе сортировки элементы последовательности меняются местами. Сортировка называется устойчивой, если на этапе замены два одинаковых ключа не меняются местами. Сортировка называется внутренней, если все сортируемые ключи размещаются в оперативной памяти. Если некоторая часть ключей размещается на внешнем носителе, то сортировка называется внешней.