Изменения

buckets[i] = Bucketsort quicksort (buckets[i],min_bucktes[i],max_buckets[i])

Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> {{---}} основание системы исчисления и количество блоков для разбиения. <tex>pn_i </tex> {{---}} случайная величина, обозначающая количество разрядов элементов попавших в объекте<tex> i </tex>-ый карман.Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем <Textex>O T(p n) </Textex> {{---}} время работы алгоритма карманной сортировки <Textex>T(n ) = \theta(n) + \sum\limits_{i = 1}^kO(n_i</tex> <tex> \log n_i)+ \theta(k)</Textex> итераций.Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> M(n_i) = n/k</tex>. Следовательно Тоесть, в средним алгоритм карманной сортировки совершает если <Textex>O (n \sim k </Textex>  <Textex>T(n) = \log_k theta(n)</Textex> действий. При этом на некотором множестве наборов Если, где <tex> k n = Oo(nk)</tex>, алгоритм отработает за линейное время.В худшем случае сортировка работает за <tex>O T(n^2) = \theta(k)</tex>.