IT1230809

Bucket sort

or bin sort, is a sorting algorithm that works by partitioning an array into a number of bucket . Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a cousin of radix sort in the most to least significant digit flavour. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. Estimates involve the number of buckets.

Run-time Complexity Analysis:
♥efficient and effective in sorting the list.

Codes:
function bucket-sort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
next-sort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]

Application:
Given an array, put the array of numbers in a bucket where they must be placed then sort the list.
Reference:
commons.wikimedia.org/wiki/File:Bucket_sort_2.png
http://en.wikipedia.org/wiki/Bucket_sort