Постановка задачи сортировки

Пусть имеется N элементов R1, R2, …, Rn - записи, т.к. для удобства в каждом из этих элементов одно поле ключевое, а вторые поля – сопутствующие, или информационные.

R1, R2, …, Rn

Важно: с точки зрения программирования доступ к полю k R[i].k тоже самое, что k[i], но R[i] ↔ R[j]

Ключ – это поле, которое управляет процессом сортировки, причем на множестве ключей (вспомним, что ключевое поле необязательно численное). Определим отношение порядка “>” таким образом, чтобы для любых трех значений ключей a,b,c выполнялись следующие законы:

1. Если, а > b и b>c то a>c – закон транзитивности
2. Справедливо одно и только одно из соотношений либо a<b либо a>b либо a=b закон трихотомии

Может быть доказано, что любое множество (ключей), на котором определены отношение порядка меньше либо больше используя законы 1 и 2, может быть упорядочено, так как эти законы определяют математическое понятие линейного упорядочивания, или по-другому – совершенно упорядочение.

Тогда задача сортировки заключается, чтобы найти такую перестановку записей, чтобы ключи k1, k2,..., kn расположились в неубывающем порядке.