chap internal sorting one could use base or base would be appropriate for sorting character strings for nowwe will treat as constant value and ignore it for the purpose of determining asymptotic complexity variable is related to the key rangeit is the maximum number of digits that key may have in base in some applications we can determine to be of limited size and so might wish to consider it constant in this caseradix sort is th(nin the bestaverageand worst casesmaking it the sort with best asymptotic complexity that we have studied is it reasonable assumption to treat as constantor is there some relationship between and nif the key range is limited and duplicate key values are commonthere might be no relationship between and to make this distinction clearuse to denote the number of distinct key values used by the records thusn < because it takes minimum of logr base digits to represent distinct key valueswe know that >logr nowconsider the situation in which no keys are duplicated if there are unique keys ( )then it requires distinct code values to represent them thusk >logr because it requires at least ohm(log ndigits (within constant factorto distinguish between the distinct keysk is in ohm(log nthis yields an asymptotic complexity of ohm( log nfor radix sort to process distinct key values it is possible that the key range is much largerlogr bits is merely the best case possible for distinct values thusthe logr estimate for could be overly optimistic the moral of this analysis is thatfor the general case of distinct key valuesradix sort is at best ohm( log nsorting algorithm radix sort can be much improved by making base be as large as possible consider the case of an integer key value set for some in other wordsthe value of is related to the number of bits of the key processed on each pass each time the number of bits is doubledthe number of passes is cut in half when processing an integer key valuesetting allows the key to be processed one byte at time processing -bit key requires only four passes it is not unreasonable on most computers to use kresulting in only two passes for -bit key of coursethis requires cnt array of size performance will be good only if the number of records is close to or greater in other wordsthe number of records must be large compared to the key size for radix sort to be efficient in many sorting applicationsradix sort can be tuned in this way to give good performance radix sort depends on the ability to make fixed number of multiway choices based on digit valueas well as random access to the bins thusradix sort might be difficult to implement for certain key types for exampleif the keys