bucket-sort and radix-sort in the previous sectionwe showed that ohm(nlogntime is necessaryin the worst caseto sort an -element sequence with comparison-based sorting algorithm natural question to askthenis whether there are other kinds of sorting algorithms that can be designed to run asymptotically faster than (nlogntime interestinglysuch algorithms existbut they require special assumptions about the input sequence to be sorted even sosuch scenarios often arise in practiceso discussing them is worthwhile in this sectionwe consider the problem of sorting sequence of entrieseach key-value pair bucket-sort consider sequence of entries whose keys are integers in the range [ , ]for some integer > and suppose that should be sorted according to the keys of the entries in this caseit is possible to sort in ( ntime it might seem surprisingbut this impliesfor examplethat if is ( )then we can sort in (ntime of coursethe crucial point is thatbecause of the restrictive assumption about the format of the elementswe can avoid using comparisons the main idea is to use an algorithm called bucket-sortwhich is not based on comparisonsbut on using keys as indices into bucket array that has cells indexed from to an entry with key is placed in the "bucketb[ ]which