1. Общие понятия
 

Сортировку следует понимать как процесс перегруппировки однотипных элементов структуры данных в некотором определенном порядке. Цель сортировки - облегчить последующий поиск, обновление, исключение, включение элементов в структуру данных. На отсортированных данных легче определить, имеются ли пропущенные элементы, все ли элементы проверены, легче найти общие элементы двух однотипных структур, слить их воедино. Сортировка является важным средством ускорения работы практически любого алгоритма, в котором требуется частое обращение к определенным элементам структуры данных.

Разработано множество алгоритмов сортировки, однако нет алгоритма, который был бы наилучшим в любом случае. Эффективность алгоритма сортировки может зависеть от ряда факторов, таких, как: число сортируемых элементов; диапазон и распределение значений сортируемых элементов; степень отсортированности элементов; характеристики алгоритма (сложность, требования к памяти и т.п.); место размещения элементов (в оперативной памяти или на ВЗУ).

В зависимости от последнего фактора все методы сортировки разбивают на два класса: внутренняя сортировка (сортировка массивов) и внешняя сортировка (сортировка файлов, или сортировка последовательностей).

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

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