 Note that if k is chosen to be formula_28, then bucket sort runs in formula_3 average time, given a uniformly distributed input.A common optimization is to put the unsorted elements of the buckets back in the original array "first", then run insertion sort over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.The most common variant of bucket sort operates on a list of "n" numeric inputs between zero and some maximum value "M" and divides the value range into "n" buckets each of size "M"/"n".