217
Сортировка вставкой
1. Хотя существуют универсальные алгоритмы, хорошо работа-
ющие с подавляющим большинством приложений, есть два
алгоритма специального назначения, которые иногда могут
понадобиться: поразрядная сортировка (radix sort) и ограни-
ченная пирамидальная сортировка (bounded heap sort).
2. Один алгоритм сортировки, сортировка слиянием (merge
sort) — прекрасный обучающий пример, поскольку демон-
стрирует важную и полезную стратегию для разработки ал-
горитмов под названием «разделяй — властвуй — соединяй»
(divide — conquer — glue). Кроме того, когда мы проанализиру-
ем его производительность, вы узнаете о порядке роста, кото-
рого не видели раньше, — линейно-логарифмическом. Наконец,
часть наиболее широко используемых алгоритмов ...