Сортировка - преобразование последовательности элементов в неубывающую (или невозрастающую) последовательность. Последовательность элементов {A_i} называют неубывающей, если для любых i и j, таких что i < j выполняется неравенство A_i ≤ A_j. Для строго возрастающей последовательности неравенство принимает вид A_i < A_j. Аналогичным образом определяется невозрастающая и убывающая последовательности.

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

Для лучшего понимания того, в каких случаях нужно применить тот или иной алгоритм необходимо знать, что понимают под показателем сложности алгоритма. Речь идет о том, как зависит число операций, которые нужно произвести согласно алгоритму от объема данных, в нашем случае от количества элементов массива N. Сложность задачи может быть логарифмической, линейной, квадратичной, экспонициальной и т.д., где для решения задачи необходимо выполнение O(ln(N)), O(N), O(N²) и O(e^N) операций соответственно. Например, квадратичный порядок сложности O(N²) означает, что задача может использовать N² операций, а может и 100*N², здесь коэффициент перед N² не имеет значения: важен порядок, важно знать во сколько раз программа будет работать дольше, если число N увеличится вдвое, втрое или в 10 раз. В нашем случае независимо от этого коэффициента получим, что программа будет выполняться соответственно в 4, 9 и 100 раз дольше.

Наилучшие универсальные алгоритмы сортировки имеют порядок сложности O(n×ln(n)), что позволяет в олимпиадных задачах сортировать массивы для N = 300 000 (приблизительно). В качестве примера подобных алгоритмов можно привести следующие сортировки: быстрая, пирамидальная, слиянием, бинарным деревом.

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

В частных случаях отсортировать данные возможно с линейным порядком сложности, когда есть некоторые ограничения на данные (например, массив уже частично отсортирован или диапазон элементов массива ограничен). С таким порядком сложности возможна сортировка массива, состоящего из 10⁷ элементов! Например, следующие алгоритмы дают такой результат: цифровая и поразрядная сортировки.

Многие считают, что достаточно знания двух сортировок (например, "пузырьком" и "быстрой"), чтобы решать любые олимпиадные задачи. Но на самом деле это далеко не так. Далее, мы будем рассматривать алгоритмы сортировки, наиболее часто используемые в программировании. Во всех темах раздела "Сортировка" будем упорядочивать элементы по неубыванию полагая, что a[i] - целочисленный массив, состоящий из n элементов, с индексами от 0 до n-1. В языке C++ такой массив может быть описан, например, следующим образом: