Editing Bucket sort (section)

==Pseudocode==

 '''function''' bucketSort(array, k) '''is'''
     buckets ← new array of k empty lists
     M ← 1 + the maximum key value in the array
     '''for''' i = 0 '''to''' length(array) '''do'''
         insert ''array[i]'' into ''buckets[floor(k × array[i] / M)]''
     '''for''' i = 0 '''to''' k '''do''' 
         nextSort(buckets[i])
     '''return''' the concatenation of buckets[0], ...., buckets[k]

Let ''array'' denote the array to be sorted and ''k'' denote the number of buckets to use. One can compute the maximum key value in [[linear time]] by iterating over all the keys once. The [[floor function]] must be used to convert a floating number to an integer ( and possibly casting of datatypes too ). The function ''nextSort'' is a sorting function used to sort each bucket. Conventionally, [[insertion sort]] is used, but other algorithms could be used as well, such as ''[[selection sort]]'' or ''[[merge sort]]''. Using ''bucketSort'' itself as ''nextSort'' produces a relative of [[radix sort]]; in particular, the case ''n = 2'' corresponds to [[quicksort]] (although potentially with poor pivot choices).