chap internal sorting as with mergesortan efficient implementation of radix sort is somewhat difficult to achieve in particularwe would prefer to sort an array of values and avoid processing linked lists if we know how many values will be in each binthen an auxiliary array of size can be used to hold the bins for exampleif during the first pass the bin will receive three records and the bin will receive five recordsthen we could simply reserve the first three array positions for the bin and the next five array positions for the bin exactly this approach is taken by the following java implementation at the end of each passthe records are copied back to the original array static void radix(integer[ainteger[bint kint rint[count/count[istores number of records in bin[iint ijrtokfor ( = rtok= <ki++rtok*= /for digits for ( = <rj++count[ /initialize count /count the number of records for each bin on this pass for ( = < lengthj++count[( [ ]/rtok)% ]++/count[jwill be index in for last slot of bin for ( = <rj++count[jcount[ - count[ ]/put records into binsworking from bottom of bin /since bins fill from bottomj counts downwards for ( = length- >= -- [--count[( [ ]/rtok)% ] [ ]for ( = < lengthj++ [jb[ ]/copy back the first inner for loop initializes array cnt the second loop counts the number of records to be assigned to each bin the third loop sets the values in cnt to their proper indices within array note that the index stored in cnt[jis the last index for bin jbins are filled from the bottom the fourth loop assigns the records to the bins (within array bthe final loop simply copies the records back to array to be ready for the next pass variable rtoi stores ri for use in bin computation on the 'th iteration figure shows how this algorithm processes the input shown in figure this algorithm requires passes over the list of numbers in base rwith th( rwork done at each pass thus the total work is th(nk rkwhat is this in terms of nbecause is the size of the baseit might be rather small