Чтобы воспользоваться эффективными алгоритмами поиска, данные должны быть упорядочены в том или ином порядке, иначе говоря, отсортированы.

Сортировка (или упорядочение), также как и поиск, является одной из часто используемых при обработке данных операций и применяется ко многим структурам данных: массивам, связным спискам, деревьям и графам.

Существуют свидетельства, что первой программой для ЭВМ с хранимой программой (с архитектурой Джона фон Неймана) была именно программа сортировки.

Количество алгоритмов сортировки достаточно велико. В книге Дональда Кнута "Искусство программирования для ЭВМ" рассматривается более двадцати (~25) алгоритмов сортировки. В настоящее время это число ещё больше увеличилось, и, вместе с экзотическими и мало распространёнными алгоритмами, приближается к 40 (и даже уже превышает 40, а с модификациями ещё больше, 42-44, скорее всего и эти цифры заниженные). Все эти алгоритмы можно классифицировать по нескольким признакам.

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

2. В зависимости от того, какая структура данных подвергается сортировке, может быть сортировка бывает массива, связного списка, дерева (пирамиды), графа.

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

4. По особенностям функциональной реализации алгоритмы сортировки делятся на группы:

Основные:
− сортировка перестановками (обменная);
− сортировка выбором (отбором);
− сортировка вставками;

Неосновные:
− сортировка подсчетом;
− сортировка слиянием;
− распределяющая сортировка.

5. По широте применения − универсальные (большинство перечисленных выше групп алгоритмов) и алгоритмы для конкретных случаев, не универсальные.

6. По признаку перестановки совпадающих данных в процессе сортировки − алгоритмы, не меняющие порядок следования совпадающих ключей (иногда такие алгоритмы не совсем удачно называют "устойчивыми" или "стабильными"), например, сортировка вставками, и меняющие порядок следования ("неустойчивые").

7. По характеру зависимости времени работы от размера N структуры данных:
− O(N²) − N‐квадратичные (это самые простые алгоритмы из 1-х трёх функциональных групп);
− O(N^k), где 1<k<2 (например, k = 1,6667 или k = 1,5 или k = 1,27 и т.п. − это алгоритм Шелла); возможен также случай, когда k = 3 − это один из самых неудачных и неэффективных алгоритмов, который получил название глупая сортировка (или дурацкая сортировка);
− O(log₂N) − логарифмические (например, быстрая сортировка или пирамидальная сортировка).

Возможны также некоторые другие принципы разделения алгоритмов сортировки.

Большинство алгоритмов имеет модификации. В книге Дональда Кнута упоминаются более двадцати алгоритмов внутренней сортировки и их комбинации.

При таком большом разнообразии важными оказываются критерии выбора алгоритма:
− средняя скорость сортировки (среднее время, удельная скорость);
− скорость в лучшем и худшем случаях (или минимальное и максимальное время);
− естественность поведения;
− переставляются ли элементы с совпадающими значениями (ключами).

Скорость (или время) сортировки определяется количеством операций сравнения и перестановки. У разных алгоритмов время работы находится в экспоненциальной или логарифмической зависимости от числа элементов структуры данных (массива) N.
Лучший случай − это ситуация, когда структура данных уже отсортирована в нужном порядке, худший случай − структура данных отсортирована в порядке, обратном требуемому. Время в лучшем и худшем случаях важны, если возможно частое повторение одной из этих ситуации. Часто при хорошей средней скорости алгоритмы имеют неприемлемую скорость в худшем случае.
Естественность поведения означает, что если массив уже упорядочен, должно выполняться минимальное число операций (в идеале 0). Максимальное число операций выполняется, если массив отсортирован в обратном порядке.

Кроме перечисленных критериев при выборе алгоритма следует принимать во внимание:
− размер структуры данных, которую предстоит сортировать (некоторые алгоритмы, высокоэффективные в средних случаях, например быстрая сортировка, не показывают своей высокой эффективности для массивов малого размера);
− степень исходной упорядоченности сортируемых данных;
− требования к необходимой памяти (разным алгоритмам может требоваться O(1), O(N) или O(N²) памяти машины);
− трудоёмкость реализации алгоритма в сравнении со сложность решаемой в программе задачи (например, пирамидальная сортировка является одним из самых сложных алгоритмов).