Take the 2-minute tour ×

Bucket sort with k buckets is O(n + k), on numbers if they are drawn uniformly from [0,1], and the number of buckets grows with the number of inputs. It seems like this should generalize pretty readily, does a distribution sort always run need O(n) work if the distribution it assumes matches the data's distribution?

If so, are there algorithms that take advantage of this by first building an approximate distribution for the data? Say by randomly a number of points from the data?

share|improve this question
Just noting that bucket sort is technically O(n+k) (k is number of buckets). –  Dukeling Dec 27 '12 at 13:37
add comment


Your Answer



Browse other questions tagged or ask your own question.