Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.
==Примечания==
Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления.
[[Быстрая сортировка|Быстрая сортировка]] является частным случаем карманной сортировки, в случае разбиения всех элементов на <tex>2 </tex> кармана. Также стоит отметить, что по принципу своей работы Bucket sort схожа с [[Цифровая сортировка|Цифровой сортировкой]].
==Ссылки==
* http://en.wikipedia.org/wiki/Bucket_sort
