arrays it' not likely there will be exactly the same number of sand so on in every digit positionso it' hard to know how big to make the arrays one way to solve this problem is to use linked lists instead of arrays linked lists expand and contract as needed we'll use this approach an outer loop looks at each digit of the keys in turn there are two inner loopsthe first takes the data from the array and puts it on the liststhe second copies it from the lists back to the array you need to use the right kind of linked list to keep the sub-sorts stableyou need the data to come out of each list in the same order it went in which kind of linked list makes this easywe'll leave the coding details as an exercise efficiency of the radix sort at first glance the efficiency of the radix sort seems too good to be true all you do is copy the original data from the array to the lists and back again if there are data itemsthis is copies you repeat this procedure once for each digit if you assumesay -digit numbersthen you'll have * equals copies if you have data itemsthere are * equals , copies the number of copies is proportional to the number of data itemswhich is ( )the most efficient sorting algorithm we've seen unfortunatelyit' generally true that if you have more data itemsyou'll need longer keys if you have times as much datayou may need to add another digit to the key the number of copies is proportional to the number of data items times the number of digits in the key the number of digits is the log of the key valuesso in most situations we're back to ( *lognefficiencythe same as quicksort there are no comparisonsalthough it takes time to extract each digit from the number this must be done once for every two copies it may behoweverthat given computer can do the digit-extraction in binary more quickly than it can do comparison of courselike mergesortthe radix sort uses about twice as much memory as quicksort summary the shellsort applies the insertion sort to widely spaced elementsthen less widely spaced elementsand so on the expression -sorting means sorting every nth element sequence of numberscalled the interval sequenceor gap sequenceis used to determine the sorting intervals in the shellsort widely used interval sequence is generated by the recursive expression = * + where the initial value of is