Problem Detail: Bucket sort is a linear-time sort.
- Why do we use insertion sort in it? We know that insertion sort takes $O(n^2)$ time.
- Why can we not use any linear sort inside it?
- As we see, when in each bucket we use insertion sort $O(n^2)$. How is bucket sort’s total complexity $O(n)$?
- Why do we not use a $O(n log n)$ sort such as merge sort or quick sort?
Asked By : Jawwad Rafiq
Answered By : Hurkyl
If each bucket has $O(1)$ things, then insertion sorting the buckets takes time $O(n)$. As a more practical matter, the algorithm you use to sort small lists of things should be chosen because it’s fast at sorting small lists of things, not for its asymptotic performance on large lists of things. And insertion sort seems to be the popular choice for this task. An implementation of bucket sort that produces buckets with many elements should indeed use some other method (e.g. bucket sort again) to sort the buckets.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48815 Ask a Question Download Related Notes/Documents
