In which of the following case pigeonhole sort is most efficient?
(a) when range of input is less than number of elements
(b) when range of input is more than number of elements
(c) when range of input is comparable to the number of elements
(d) when the given array is almost sorted
I had been asked this question during an online exam.
Question is taken from Sorting in portion Sorting of Data Structures & Algorithms II