linear-time sortingbucket-sort and radix-sort in the previous sectionwe showed that ( log ntime 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 ( log ntime interestinglysuch algorithms existbut they require special assumptions about the input sequence to be sorted even sosuch scenarios often arise in practicesuch as when sorting integers from known range or sorting character stringsso discussing them is worthwhile in this sectionwe consider the problem of sorting sequence of entrieseach key-value pairwhere the keys have restricted type 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 itself is sequence (of entries with key kafter inserting each entry of the input sequence into its bucketwe can put the entries back into in sorted order by enumerating the contents of the buckets [ ] [ ] [ in order we describe the bucket-sort algorithm in code fragment algorithm bucketsort( )inputsequence of entries with integer keys in the range [ outputsequence sorted in nondecreasing order of the keys let be an array of sequenceseach of which is initially empty for each entry in do the key of remove from and insert it at the end of bucket (sequenceb[kfor to - do for each entry in sequence [ido remove from [iand insert it at the end of code fragment bucket-sort