retagged by
431 views

1 Answer

1 votes
1 votes

 If the buckets will be small (i.e. the data is evenly distributed) then insertion sort works well. Or, if each digit can take up to k possible values and k = O(n) then counting sort allows radix sort to run in linear time.

To see this, note that if we use counting sort to sort the keys into piles, each pass is O(n). There are d passes, so if d is constant, radix sort is O(dn), which is O(n). The hidden constants can be quite large: radix sort usually makes fewer passes over the data than quicksort, but each pass of radix sort may take significantly longer, depending on the machine and the implementation.

Also, if counting sort is the intermediate stable sort, the sorting does not occur in place, so if space is limited, one might choose quicksort instead of radix sort.

For More info refer here :http://www.cs.otago.ac.nz/cosc242/pdf/lecture9.pdf

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm

Related questions

1 votes
1 votes
2 answers
1
akash.dinkar12 asked Jun 28, 2019
1,068 views
Show how to sort $n$ integers in the range $0$ to $n^3-1$ in $O(n)$ time.
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Jun 28, 2019
582 views
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
0 votes
0 votes
1 answer
3
1 votes
1 votes
1 answer
4
gatecse asked Dec 9, 2020
624 views
Consider an array of positive integers between $123456$ to $876543$, which sorting algorithm can be used to sort these number in linear time?Impossible to sort in linear ...