Analysis of Bucket Sort
lAssume that the number of data elements is comparable to, or larger than, the number of buckets.
lGo through the data once, putting each element in the corresponding list.
This is O(n).
lConcatenate the resulting lists.
This is also O(n).
lTherefore we have O(n) overall.
lRemember that bucket sorting makes special assumptions about the data.