Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode).

In the worst case, this would imply that we would have $O(n^2)$ performance, because if every element was in one bucket, then we would have to use insertion sort on $n$ elements which is $O(n^2)$.

So the first thing that comes to mind to fix the worst case running time is to not use insertion-sort, because it is $O(n^2)$. Instead we could use merge-sort or heap-sort m, because the worst case running time for both of those algorithms is $O(n\log n)$. However, if we use merge-sort and heap-sort, do they preserve the expected linear running-time of bucket-sort?

share|improve this question
The use of $O$ weakens your statements; I guess you want to use $\Theta$? –  Raphael Feb 18 '13 at 11:36
add comment

1 Answer

up vote 4 down vote accepted

You should first understand the proof that bucket sort runs in expected linear time if insertion sort is used. At some point in the proof, the worst-case running time of insertion sort shows up. See what happens when you plug in instead the worst-case running time of any other sorting algorithm.

The reason insertion sort is used in practice is that we expect the buckets to be small, and for small lists, insertion sort is much faster than anything else. Even when implementing merge sort or quicksort, insertion sort is used when the list gets small enough (say below 20 items or so).

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.