Adaptive Sort

Performance

To determine the efficiency of ASort, I have compared them in a number of different tests against efficient implementations of Quicksort and Merge sort as well as against the sorting method included in the .NET Framework which is based on quicksort. All sorting is done on arrays with integers, and all sort method uses the same comparison method.

Test Suites

To get a good estimate of the "real life" performance, I have implemented a test suite consisting of 7 different tests, and then assigned them a weight (in %) based on my own estimates. Then the values are adjusted by the weight and added to get a final performance.

The 7 different tests and their weights are:

10M Test suite in detail

Below are all the tests in the 10M test suite, showing the individual results for sorting 10M integers, together with the resulting weighted performance:

Sorting 10M random integers
Weight: 0.35

Sort algorithmSecondsComparisonsRatio %
.NET sort4.81286.90M140/125
Quicksort3.50261.48M102/114
Merge sort3.38224M98/98
ASort3.44229.74M100/100

Sorting 10M random 1 - 100 integers
Weight: 0.1

Sort algorithmSecondsComparisonsRatio %
.NET sort3.73253.22M319/275
Quicksort2.75240.16M235/260
Merge sort2.95223.31M252/242
ASort1.1792.23M100/100

Sorting 10M random 1 - 10 integers
Weight: 0.1

Sort algorithmSecondsComparisonsRatio %
.NET sort3.53252.95M526/528
Quicksort2.52234.75M374/490
Merge sort2.75215.39M409/450
ASort0.6747.86M100/100

Sorting 10M random 1 - 2 integers
Weight: 0.1

Sort algorithmSecondsComparisonsRatio %
.NET sort3.22246.35M981/924
Quicksort2.27233.88M690/877
Merge sort2.27175.39M690/658
ASort0.3326.67M100/100

Sorting 10M integers reverse sorted
Weight: 0.05

Sort algorithmSecondsComparisonsRatio %
.NET sort2.59240.64M874/691
Quicksort1.75216.85M589/623
Merge sort1.64114.43M553/329
ASort0.3034.82M100/100

Sorting 10M integers almost sorted
Weight: 0.25

Sort algorithmSecondsComparisonsRatio %
.NET sort4.02356.46M627/558
Quicksort1.92226.70M300/355
Merge sort1.88145.83M293/228
ASort0.6463.83M100/100

Sorting 10M integers 5 sorted/appended
Weight: 0.05

Sort algorithmSecondsComparisonsRatio %
.NET sort4.05297.99M762/584
Quicksort2.41237.83M453/466
Merge sort1.80135.32M338/265
ASort0.5351M100/100

Test Suite: 10M integers
Displaying values adjusted by weight.

Sort algorithmSecondsComparisonsRatio %
.NET sort4.07291.71M251/249
Quicksort2.67241.81M164/206
Merge sort2.62188.26M161/160
ASort1.62117.34M100/100

Test suites

Below are the resulting performance for sorting various list lengths. To get a reliable time, I have sorted the smaller lists (<1M) several times.

The columns contain the name of the algorithm, the time in second (adjusted by weight), the number of comparisons (adjusted by weight) and the ratio in % compared to the base which is my ASort. All values are the sum of the 7 individual test case values.

Test Suite: 5000 * 1k integers.

Sort algorithmSecondsComparisonsRatio %
.NET sort1.0864.11M207/177
Quicksort0.6949.83M132/138
Merge sort0.6339.41M120/109
ASort0.5236.12M100/100

Test Suite: 500 * 10k integers.

Sort algorithmSecondsComparisonsRatio %
.NET sort1.3382.58M233/199
Quicksort0.8867.07M153/161
Merge sort0.7754.68M135/132
ASort0.5741.56M100/100

Test Suite: 50 * 100k integers.

Sort algorithmSecondsComparisonsRatio %
.NET sort1.54106.47M231/224
Quicksort1.0086.08M150/181
Merge sort0.9567.40M142/142
ASort0.6747.55M100/100

Test Suite: 1M integers.

Sort algorithmSecondsComparisonsRatio %
.NET sort0.3525.07M242/236
Quicksort0.2320.89M161/197
Merge sort0.2215.89M151/150
ASort0.1510.61M100/100

Test Suite: 10M integers.

Sort algorithmSecondsComparisonsRatio %
.NET sort4.07291.71M251/249
Quicksort2.67241.81M164/206
Merge sort2.62188.26M161/160
ASort1.62117.34M100/100

Test Suite: 100M integers.

Sort algorithmSecondsComparisonsRatio %
.NET sort46.363.39G261/255
Quicksort30.502.78G172/209
Merge sort29.362.12G165/160
ASort17.781.33G100/100

Every test was run on a 2.4GHz Quad Intel processor, using one thread (no multithreading so far). The ASort algorithm is implemented in pure C#.NET without using any external .dll or unsafe code (the same way as Quicksort and Merge sort is implemented).

Efficiency graph - Comparisons

The graph below shows the sorting algorithms and their comparison efficiency as the number of values to sort increase. Note that while ASort isn't that much better compared to Quicksort and Merge sort on small lists, it quickly increases its relative efficiency.

Efficiency graph - Time

The graph below shows the sorting algorithms and their time efficiency as the number of values to sort increase. Note that while quicksort and merge sort differ a lot on number of comparisons, they are very close in time efficiency. As in the previous graph, ASort quickly pulls ahead.

Efficiency graph - Comparisons versus Θ(nlogn) coefficient

The graph below shows the sorting algorithms and how their Θ(nlogn) coefficient (the Y axis) changes as the number of elements grows. As expected, all 3 general purpose sorting algorithms have a fairly constant coefficient, while ASort improves its efficiency versus Θ(nlogn) as the number of elements increases.