2.9.2 Анализ времени работы

Оценим время работы алгоритма сортировки подсчётом. Циклы в стро­ках 1-2 и 6-7 работают за время О(k), циклы в строках 3-4 и 10-11 – за время О(п), а весь алгоритм, стало быть, работает за время О(k + п). Если k =О(п), то время работы есть О(п).

Алгоритм сортировки подсчётом обладает важным свойством, называемым устойчивостью (is stable). Именно, если во входном массиве присутствует не­сколько равных чисел, то в выходном массиве они стоят в том же порядке, что и во входном. Это свойство имеет смысл, только если в массиве вместе с числами записаны дополнительные данные. К примеру, сортируются не просто числа, а пары , где t – число от 1 до k, а х – про­извольный объект, и требуется переставить их так, чтобы первые компоненты пар шли в неубывающем порядке. Описанный алгоритм позволяет это сделать, причём относительное расположение пар с равными первыми компонентами не меняется. Это свойство и называется устойчивостью.