В статье рассматривается алгоритм сортировки методом индексов в аспекте его трудоемкости в среднем. Для построения аналитической функции трудоемкости исследуется дискретное распределение вероятностей размаха варьирования в целочисленном массиве, имеющее самостоятельный теоретический интерес. Полученное распределение является базой для исследования трудоемкости алгоритма сортировки индексами, обладающего, в частных случаях, линейной сложностью по длине входа.