chap internal sorting sort insertion bubble selection shell shell/ merge merge/ quick quick/ heap heap/ radix/ radix/ up down figure empirical comparison of sorting algorithms run on -ghz intel pentium cpu running linux shellsortquicksortmergesortand heapsort each are shown with regular and optimized versions radix sort is shown for and -bit-per-pass versions all times shown are milliseconds sublists below length nine the first heapsort version uses the class definitions from section the second version removes all the class definitions and operates directly on the array using inlined code for all access functions in all casesthe values sorted are random -bit numbers the input to each algorithm is random array of integers this affects the timing for some of the sorting algorithms for exampleselection sort is not being used to best advantage because the record size is smallso it does not get the best possible showing the radix sort implementation certainly takes advantage of this key range in that it does not look at more digits than necessary on the other handit was not optimized to use bit shifting instead of divisioneven though the bases used would permit this the various sorting algorithms are shown for lists of sizes , , and , , the final two columns of each figure show the performance for the algorithms when run on inputs of size , where the numbers are in ascending (sortedand descending (reverse sortedorderrespectively these columns demonstrate best-case performance for some algorithms and worstcase performance for others these columns also show that for some algorithmsthe order of input has little effect these figures show number of interesting results as expectedthe ( sorts are quite poor performers for large arrays insertion sort is by far the best of this groupunless the array is already reverse sorted shellsort is clearly superior to any of these ( sorts for lists of even elements optimized quicksort is clearly the best overall algorithm for all but lists of elements even for small