Все алгоритмы сортировки можно поделить на две группы: сортировка сравнениями и лексикографическая сортировка. Эти два вида алгоритмов отличаются тем, что при сортировке сравнениями неизвестна внутренняя структура объектов. При этом они вообще могут иметь различную структуру, необходимо только уметь сравнивать объекты друг с другом (например, числа). На самом деле только одного сравнения объектов недостаточно, оно должно обладать еще некоторыми дополнительными свойствами, например транзитивностью, т.е. если a<b и b<c, то должно быть a<c. Предположим, что мы должны сравнивать вектора фактически являющиеся парами чисел вида r=(x,y). Определим операцию сравнения двух объектов r1=(x1,y1) и r2=(x2,y2) так: r1<r2 тогда и только тогда, когда x1<x2 или y1<y2. Удовлетворяет ли такое сравнение вышеприведенному условию? Возьмем 3 вектора: a=(3,9), b=(4,7), c=(1,8). По описанному способу сравнения получаем: a<b, b<c, но a не меньше c. Таким образом, при выборе этого отношения порядка не в каждом случае можно упорядочить заданную последовательность элементов.
Лексикографическая сортировка обычно применяется при сортировке объектов с известной внутренней структурой. Например, упорядочивание текстовых строк по алфавиту. Внутренняя структура строк известна: строка состоит из символов; количество символов алфавита ограничено.
