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?

  • $\begingroup$ The use of $O$ weakens your statements; I guess you want to use $\Theta$? $\endgroup$
    – Raphael
    Commented Feb 18, 2013 at 11:36

1 Answer 1


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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