В общем случае под сортировкой понимается перестановка элементов А₁, А₂, А₃, ... , А_n в таком порядке, A k₁, A k₂, A k₃, ..., A k_n, что при заданной функции упорядочения F справедливо отношение F ( A k₁ ) £ F ( A k₂ ) £ F ( A k₃ ) £ ... £ F ( A k_n ). Обычно функция упорядочения не вычисляется по какому-то специальному правилу, а держится в каждом сортируемом элементе в виде явной компоненты (ключа).

Основной целью сортировки последовательности является увеличение эффективности поиска в уже отсортированной последовательности.

Алгоритмы сортировки могут быть классифицированы следующим образом:

Разделение алгоритмов сортировки на внешние и внутренние обусловлено разницей свойств типов данных сортируемых последовательностей.

Методы внутренней сортировки ориентированы на сортировку массивов. При этом используются свойства типов данных "массив", позволяющие работать со всеми его элементами, находящимися в оперативной памяти. Разделение методов внутренней сортировки на сложные (модифицированные) и простые связано с оценкой эффективности алгоритмов по двум основным параметрам:

1. число сравнений ключей элементов;
2. число перестановок элементов.

Для простых методов сортировки эти параметры имеют порядок в среднем n2, а для сложных (модифицированных) - n*logn, где n-количество сортируемых ключей.

Методы внешней сортировки ориентированны на сортировку файлов и предполагают, что доступ к элементам файла осуществляется последовательно. Основой всех алгоритмов внешней сортировки является выполнение следующих фаз обработки входного файла:

• фаза разбиения входной последовательности;
• фаза слияния серий элементов.