Query, update, navigate, and manage all databases from one database
client with ease using RazorSQL, a database query tool, SQL Editor,
database navigator, and administraton tool. Download a free trial today!
The text editor for programmers with coding tools and support for over 20 languages. Download a free trial today!
Sorting Suite Timing Data
NOTE: This timing data was compiled on a Pentium III 700 MHZ computer with 256 MB RAM running JDK 1.3. The timing was done using a high-resolution timer native to the Windows operating system. This high-res timer gives sub-thousandth-of-a-second timing ability. The high-res timer is NOT included with the download.
This timing data is not guaranteed to be consistent across hardware, operating systems, or even virtual machines. This timing data is provided to give a general idea on the performance of the sorting algorithms on a particular machine. As such, one can be reasonably sure that the algorithms will perform consistently with the data below, relative to each other, on most architecutes. For example, if QuickInsertionSort is the fastest sorting algorithm for int arrays of size 20000 on a Pentium III running on Windows 2000, there is a good possibility it will also be the fastest sorting algorithm for int arrays of size 20000 on a Sun Sparc4 with 4 336 mhz processors.
NOTE: In the tables below, each column represents one of the sorting algorithms as shown in the key below. Each row represents the size of the data structure that was sorted. Each table corresponds to a data structure of a different data type. These are the following:
Data Type = array of ints
Array Sizes = 10, 50, 100, 500, 1000, 2000, 10000, 20000
Data Type = array of Objects, sorted using only a java.util.Comparator for the given Object (See the user's guide for more details)
Array Sizes = 10, 50, 100, 500, 1000, 2000, 10000
Data Type = array of Objects, sorted using Reflection to get the value of the result of a call to a method name on the passed in Object. (See the user's guide for more details)
Array Sizes = 10, 50, 100, 500, 1000
Data Type = List of Objects, sorted using only a java.util.Comparator for the given List. (See the user's guide for more details)
Array Sizes = 10, 50, 100, 500, 1000, 2000, 10000
NOTE: In each of the tables below, the data sorted was generated using the com.rp.util.test.RandomArrayGenerator class. This class generates arrays of random data given a data type and an array size.
KEY: QIS= QuickInsertionSort, QS = QuickSort, QSM3 = QuickSortMedian3, QSR = QuickSortRandom COMB = CombSort, MIS = MergeInsertionSort, MERG = MergeSort, HEAP = HeapSort, SH = ShellSort, INSB = InsertionSortBinarySearch, INS = InsertionSort, SEL = SelectionSort, BU = BubbleSort
Time is in microseconds. (i.e. 8.22 = 0.00822 seconds)
TABLE 1 DATA TYPE = int
Table 2 Data type = Object (Using a Comparator and no Reflection)
Table 3 Data type = Object (Using a Comparator and Reflection for method values)
Table 4 Data type = List
As can be seen from the timing data above, on average, the QuickSort variants are the fastest sorting algorithms, with QuickInsertionSort a clear winner, especially for large data sets. It should be mentioned, however, that the QuickSort algorithm is susceptible to executing n2 comparisons for input ordered in a certain way. QuickSortRandom uses a technique to lower the probability of this n2 occurrence to virtually zero. Note that on average QuickSortRandom is slower than regular QuickSort, due to the increased overhead of the random number generation involved in the QuickSortRandom algorithm. The fastest, QuickInsertionSort, uses InsertionSort to sort small input, since InsertionSort is faster than QuickSort for small input. The threshold at which to switch from QuickSort to InsertionSort is a value best optimized on a per-machine basis. In these tests, this value was set at 10.
The next grouping on the performance list are CombSort, HeapSort, MergeInsertionSort, and MergeSort. MergeSort and HeapSort both run in worst-case nlog2n comparisons, with MergeInsertionSort following suit for large input. Of the three, MergeInsertionSort is generally the fastest, since it optimizes MergeSort by using InsertionSort to sort small input, since InsertionSort is faster than MergeSort for small input. Once again, the threshold at which to switch from MergeSort to InsertionSort is value best optimized on a per-machine basis. In these tests, the value was set at 30. Even though the Merge, MergeInsertionSort, and HeapSort algorithms execute an optimal number of worst-case comparisons, they suffer from one drawback: they require use of auxillary storage. Neither the QuickSort variants mentioned above nor CombSort suffer from this. In practice on average, CombSort performs remarkably well, and actually outperforms the nlog2n algorithms mentioned above.
The last grouping of algorithms as far as peformance goes contains InsertionSort, InsertionSortBinarySearch, ShellSort, SelectionSort, and BubbleSort. In practice, these algorithms are usually only attractive for sorting small input, as can be seen by their respective times in the tables above.
One interesting note that can be seen from the timing data is the great expense of using Reflection. For example, using Reflection to sort an array of Objects of size 1000 takes over 100 times longer than simply using a comparator. For small input and/or cases where peformance is not that important, using the Reflection sorting methods is more convenient. However, as shown from the data above, it probably should not be used if the aforementioned criteria is not met.
Notice that the sorting of java.util.Lists takes longer than the sorting of Object arrays. A note to be made here is that the sorting of Lists takes longer even if we start with a List, convert it to an array, and then do the sort. Thus, for applications trying to squeeze out every last bit of performance, it is actually faster to convert java.util.Lists to arrays and then sorting, as opposed to sorting the List directly.