Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Дан массив A из n элементов:
,
Будем считать, что с каждым элементом (помимо другой информации, не влияющей на сортировку) связан ключ . На множестве ключей задано отношение порядка — линейного (или совершенного) упорядочивания, для которого были бы выполнены следующие условия:
закон трихотомии: для любых либо , либо , либо ;
транзитивность: для любых если и , то .
Задачей сортировки по неубыванию является нахождение перестановки элементов с индексами от , при которой ключи располагаются в порядке неубывания:
[3]
В результате работы алгоритма и применения перестановки получается отсортированный массив:
Аналогично можно определить сортировку по невозрастанию.