Изменения

Его трудоемкость, таким образом, равна <tex>\Theta(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k = O(n)</tex>, поэтому можно считать время работы алгоритма равным <tex>\Theta(n)</tex>. <br>

Как и в обычной сортировке подсчетом, требуется <tex>\Theta(n + k)</tex> дополнительной памяти {{---}} на хранение массива <tex>B</tex> размера <tex>n</tex> и массива <tex>P</tex> размера <tex>k</tex>.

== Поиск диапазона ключей ==