Алгоритмы и структуры данных на С++. Аксёнова Е.А - 58 стр.

                 Глава 5.      Сортировка

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

   Пусть дано конечное множество записей R1 , R2 , ..., Rn и линейно
упорядоченное множество ключей K1 , K2 , ..., Kn , которое взаимно од-
нозначно отображается на множество записей. Задача сортировки –
найти такую перестановку записей Ri1 , Ri2 , ..., Rin , чтобы выполня-
лось неравенство Ki1 ≤ Ki2 ≤ ... ≤ Kin .
   В качестве примера можно привести задачу сортировки телефон-
ного справочника. Тогда R1 , R2 , ..., Rn – это номера телефонов, адреса
и фамилии абонентов, а K1 , K2 , ..., Kn – это лексикографически упо-
рядоченное множество фамилий абонентов.
   Сортировка называется устойчивой, если записи с равными клю-
чами остаются на месте.
   Если записи и/или ключи занимают память большого размера,
то лучше составить новую таблицу адресов и работать только с ней,
не перемещая записи (на рис. 5.1 сегменты). Такой метод называется
сортировкой таблицы адресов.




                               Рис. 5.1

   Если в каждой записи организовать вспомогательное поле связи,
то можно работать только со связями, не перемещая записи. Такой
метод называется сортировкой списка.