Sorting Suite Timing Data

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:

Table 1:
Data Type = array of ints
Array Sizes = 10, 50, 100, 500, 1000, 2000, 10000, 20000

Table 2:
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

Table 3:
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

Table 4:
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

CLASS NAME: QIS QS QSM3 QSR COMB MIS MERG HEAP SH INSB INS SEL BU
10 0.0028  0.0040  0.0042  0.0052  0.0037  0.0030  0.0070  0.0057  0.0034  0.0054  0.0028  0.0035  0.0037 
50 0.0120 0.0175 0.0251 0.0194 0.0496 0.0410 0.0310 0.0165 0.0136 0.0372 0.0177 0.0244 0.0429
100 0.0258 0.0380 0.0510 0.0410 0.0348 0.0870 0.0680 0.0360 0.0360 0.1026 0.0605 0.0844 0.1642
500 0.1587 0.2200 0.2874 0.2335 0.2536 1.0220 0.4290 0.2580 0.5590 1.4220 1.3670 1.8760 4.1060
1000 0.339 0.445 0.594 0.504 0.596 1.138 0.940 0.590 2.110 4.954 5.445 7.340 16.50
2000 0.73 0.94 1.22 1.08 1.89 2.54 2.05 1.29 8.05 18.4 21.9 29.4 65.8
10000 4.11 5.20 6.40 5.79 9.08 14.9 12.3 7.90 195 430 544 725 1695
20000  8.55 10.6 13.2 11.7 20.5 32.1 26.4 17.0 779 1716 2168 2899 6596



Table 2 Data type = Object (Using a Comparator and no Reflection)

CLASS NAME: QIS QS QSM3 QSR COMB MIS MERG HEAP SH INSB INS SEL BU
10  0.010   0.013   0.015   0.018   0.010   0.013   0.020   0.010   0.009   0.010   0.010   0.014   0.014  
50  0.082 0.098 0.129 0.126 0.150 0.094 0.164 0.104 0.103 0.090 0.180 0.326 0.310
100  0.208 0.233 0.259 0.270 0.262 0.218 0.369 0.268 0.360 0.240 0.690 1.330 1.250
500  1.26 1.50 1.52 1.69 1.64 1.47 2.44 1.97 6.59 3.02 16.3 31.8 32.0
1000  2.95 3.14 3.43 3.74 4.09 3.30 5.46 4.41 24.9 10.4 67.6 130.7 136.1
2000  6.40 7.15 7.21 8.05 8.03 8.23 12.3 10.1 98.0 38.4 270.1 511.2 553.4
10000  41.2 44.9 47.3 49.1 54.4 63.4 81.9 116.2 2757 1318 7774 17943 20473



Table 3 Data type = Object (Using a Comparator and Reflection for method values)

CLASS NAME: QIS QS QSM3 QSR COMB MIS MERG HEAP SH INSB INS SEL BU
10  1.21 1.05 1.01 1.77 1.30 1.05 2.35 1.79 1.12 0.92 1.35 1.90 1.90
50  8.95 8.07 9.00 12.1 16.4 9.63 22.3 21.9 16.3 9.46 26.6 52.0 52.0
100  20.12 20.05 22.17 28.14 36.83 23.81 52.25 55.08 52.49 22.71 106.8 209.5 209.3
500  140.6 135.7 141.1 170.5 250.9 164.5 363.9 407.0 1030 159.7 2743 5331 5323
1000  298.9   288.1   294.9   361.4   541.9   372.8   811.7   915.7   3935   357.9   10787   21222   21208  



Table 4 Data type = List

CLASS NAME: QIS QS QSM3 QSR COMB MIS MERG HEAP SH INSB INS SEL BU
10  0.016 0.017 0.019 0.024 0.015 0.015 0.03 0.016 0.013 0.014 0.015 0.019 0.02
50  0.105 0.131 0.140 0.158 0.198 0.120 0.250 0.163 0.140 0.150 0.270 0.440 0.500
100  0.264 0.303 0.310 0.340 0.347 0.260 0.570 0.420 0.470 0.470 1.09 1.66 2.00
500  1.81 1.86 2.04 2.16 2.29 1.78 3.79 2.86 9.65 8.38 23.8 40.7 51.3
1000  4.00 4.19 4.47 4.76 5.33 4.34 8.47 6.66 36.2 30.7 97.7 164 207
2000  8.43 9.14 9.74 10.5 11.4 9.37 18.9 15.0 141 122 389 646 854
10000   50.29   56.98   58.82   62.58   63.66   73.34   123.8   146.2   3599   3345   10537   20864   26828  



Analysis

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.