На этом шаге мы приведем общие сведения об алгоритмах сортировки.

Алгоритм сортировки произвольного списка (массива, последовательности и т. д.) - одна из наиболее изученных задач в информатике. Её можно решить многими способами, которые могут использоваться, чтобы ввести основные понятия, связанные с вычислительной сложностью и анализом времени выполнения, парадигмами разработки алгоритмов или структурами данных. Алгоритмы сортировки, приведенные в следующих шагах, предполагают, что вход задачи - это список а из n вещественных чисел. Выход - перегруппировка (или перестановка) элементов, которая даёт другой список а', где а'_i ≤ a'_i+1 для i = 0, ..., n - 2 (≤ можно считать логической функцией, позволяющей определить, предшествует ли один элемент другому, и реализующей полное бинарное отношение следования). Выбор вещественного типа для элементов списка подразумевает, что алгоритмы должны выполнять сравнения операцией ≤. Можно показать, что любой алгоритм решения этой задачи требует Ω(n logn) сравнений (то есть, по крайней мере, порядка n logn проверок ≤). Наконец, есть алгоритмы сортировки, не использующие сравнение элементов и требующие Ω(n) операций. Однако для их применения элементы списка должны удовлетворять определенным условиям. Например, алгоритм "сортировки подсчётом" сортирует только целые числа, принадлежащие малому интервалу [0, k].

На следующем шаге мы рассмотрим алгоритм сортировки слиянием.