Worst case analysis of bucket sort using insertion sort for the buckets

Problem Detail: 

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?

Asked By : CodeKingPlusPlus

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9876