sorting make decisions based on ordering information only naturallyif there is extra information availablewe should expect to find more efficient algorithmsince otherwise the extra information would be wasted although bucket sort seems like much too trivial an algorithm to be usefulit turns out that there are many cases where the input is only small integersso that using method like quicksort is really overkill one such example is radix sort radix sort is sometimes known as card sort because it was used until the advent of modern computers to sort old-style punch cards suppose we have numbers in the range to that we would like to sort in general this is numbers in the range to - for some constant obviously we cannot use bucket sortthere would be too many buckets the trick is to use several passes of bucket sort the natural algorithm would be to bucket sort by the most significant "digit(digit is taken to base )then next most significantand so on but simpler idea is to perform bucket sorts in the reverse orderstarting with the least significant "digitfirst of coursemore than one number could fall into the same bucketand unlike the original bucket sortthese numbers could be differentso we keep them in list each pass is stableitems that agree in the current digit retain the ordering determined in prior passes the trace in figure shows the result of sorting which is the first ten cubes arranged randomly (we use to make clear the tens and hundreds digitsafter the first passthe items are sorted on the least significant digitand in generalafter the kth passthe items are sorted on the least significant digits so at the endthe items are completely sorted to see that the algorithm worksnotice that the only possible failure would occur if two numbers came out of the same bucket in the wrong order but the previous passes ensure that when several numbers enter bucketthey enter in sorted order according to the - least significant digits the running time is ( ( )where is the number of passesn is the number of elements to sortand is the number of buckets one application of radix sort is sorting strings if all the strings have the same length lthen by using buckets for each characterwe can implement radix sort in (nltime the most straightforward way of doing this is shown in figure in our codewe assume that all characters are asciiresiding in the first positions of the unicode character set in each passwe add an item to the appropriate bucketand then after all the buckets are populatedwe step through the buckets dumping everything back to the array notice that when bucket is populated and emptied in the next passthe order from the current pass is preserved counting radix sort is an alternative implementation of radix sort that avoids using vectors to represent buckets insteadwe maintain count of how many items would go in each bucketthis information can go into an array countso that count[kis the number of items that are in bucket then we can use another array offsetso that offset[kinitial itemssorted by ' digitsorted by ' digitsorted by ' digit figure radix sort trace