Изменения

Тогда алгоритм "Bucket sort" в процессе работы, сделает не более чем <Tex>O(p * (n + k))</Tex> итераций.Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно , в средним алгоритм "карманной сортировки" совершает <Tex>O(n * \cdot log_k n)</Tex> действий.При этом на некотором множестве наборов, где <tex> k = O(n)</tex> , алгоритм отработает за линейное время.В худшем случаи , случае сортировка работает за <tex>O(n^2)</tex>.

Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системы системе счисления.[[Быстрая сортировка|быстрая Быстрая сортировка]] является частным случаем "карманной" сортировкойсортировки, в случаи случае разбиения всех элементов на <tex>2 </tex> "кармана".Также стоит отметить, что по принципу своей работы Bucket sort схожа с [[Цифровая сортировка|Цифровой сортировкой]].