are real numbers or arbitrary length stringsthen some care will be necessary in implementation in particularradix sort will need to be careful about deciding when the "last digithas been found to distinguish among real numbersor the last character in variable length strings implementing the concept of radix sort with the trie data structure (section is most appropriate for these situations at this pointthe perceptive reader might begin to question our earlier assumption that key comparison takes constant time if the keys are "normal integervalues stored insayan integer variablewhat is the size of this variable compared to nin factit is almost certain that (the number of bits in standard int variableis greater than log for any practical computation in this sensecomparison of two long integers requires ohm(log nwork computers normally do arithmetic in units of particular sizesuch as -bit word regardless of the size of the variablescomparisons use this native word size and require constant amount of time in practicecomparisons of two -bit values take constant timeeven though is much greater than log to some extent the truth of the proposition that there are constant time operations (such as integer comparisonis in the eye of the beholder at the gate level of computer architectureindividual bits are compared howeverconstant time comparison for integers is true in practice on most computersand we rely on such assumptions as the basis for our analyses in contrastradix sort must do several arithmetic calculations on key values (each requiring constant time)where the number of such calculations is proportional to the key length thusradix sort truly does ohm( log nwork to process distinct key values an empirical comparison of sorting algorithms which sorting algorithm is fastestasymptotic complexity analysis lets us distinguish between th( and th( log nalgorithmsbut it does not help distinguish between algorithms with the same asymptotic complexity nor does asymptotic analysis say anything about which algorithm is best for sorting small lists for answers to these questionswe can turn to empirical testing figure shows timing results for actual implementations of the sorting algorithms presented in this the algorithms compared include insertion sortbubble sortselection sortshellsortquicksortmergesortheapsort and radix sort shellsort shows both the basic version from section and another with increments based on division by three mergesort shows both the basic implementation from section and the optimized version with calls to insertion sort for lists of length below nine for quicksorttwo versions are comparedthe basic implementation from section and an optimized version that does not partition