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.

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:

- 35% for random data with no duplicate values.
- 10% each for random data with 100, 10 and 2 unique values respectively.
- 25% for almost sorted data.
- 5% for reversely sorted data.
- 5% for 5 sorted list appended together.

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 algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 4.81 | 286.90M | 140/125 |

Quicksort | 3.50 | 261.48M | 102/114 |

Merge sort | 3.38 | 224M | 98/98 |

ASort | 3.44 | 229.74M | 100/100 |

Sorting 10M random 1 - 100 integers

Weight: 0.1

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 3.73 | 253.22M | 319/275 |

Quicksort | 2.75 | 240.16M | 235/260 |

Merge sort | 2.95 | 223.31M | 252/242 |

ASort | 1.17 | 92.23M | 100/100 |

Sorting 10M random 1 - 10 integers

Weight: 0.1

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 3.53 | 252.95M | 526/528 |

Quicksort | 2.52 | 234.75M | 374/490 |

Merge sort | 2.75 | 215.39M | 409/450 |

ASort | 0.67 | 47.86M | 100/100 |

Sorting 10M random 1 - 2 integers

Weight: 0.1

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 3.22 | 246.35M | 981/924 |

Quicksort | 2.27 | 233.88M | 690/877 |

Merge sort | 2.27 | 175.39M | 690/658 |

ASort | 0.33 | 26.67M | 100/100 |

Sorting 10M integers reverse sorted

Weight: 0.05

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 2.59 | 240.64M | 874/691 |

Quicksort | 1.75 | 216.85M | 589/623 |

Merge sort | 1.64 | 114.43M | 553/329 |

ASort | 0.30 | 34.82M | 100/100 |

Sorting 10M integers almost sorted

Weight: 0.25

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 4.02 | 356.46M | 627/558 |

Quicksort | 1.92 | 226.70M | 300/355 |

Merge sort | 1.88 | 145.83M | 293/228 |

ASort | 0.64 | 63.83M | 100/100 |

Sorting 10M integers 5 sorted/appended

Weight: 0.05

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 4.05 | 297.99M | 762/584 |

Quicksort | 2.41 | 237.83M | 453/466 |

Merge sort | 1.80 | 135.32M | 338/265 |

ASort | 0.53 | 51M | 100/100 |

Test Suite: 10M integers

Displaying values adjusted by weight.

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 4.07 | 291.71M | 251/249 |

Quicksort | 2.67 | 241.81M | 164/206 |

Merge sort | 2.62 | 188.26M | 161/160 |

ASort | 1.62 | 117.34M | 100/100 |

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 algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 1.08 | 64.11M | 207/177 |

Quicksort | 0.69 | 49.83M | 132/138 |

Merge sort | 0.63 | 39.41M | 120/109 |

ASort | 0.52 | 36.12M | 100/100 |

Test Suite: 500 * 10k integers.

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 1.33 | 82.58M | 233/199 |

Quicksort | 0.88 | 67.07M | 153/161 |

Merge sort | 0.77 | 54.68M | 135/132 |

ASort | 0.57 | 41.56M | 100/100 |

Test Suite: 50 * 100k integers.

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 1.54 | 106.47M | 231/224 |

Quicksort | 1.00 | 86.08M | 150/181 |

Merge sort | 0.95 | 67.40M | 142/142 |

ASort | 0.67 | 47.55M | 100/100 |

Test Suite: 1M integers.

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 0.35 | 25.07M | 242/236 |

Quicksort | 0.23 | 20.89M | 161/197 |

Merge sort | 0.22 | 15.89M | 151/150 |

ASort | 0.15 | 10.61M | 100/100 |

Test Suite: 10M integers.

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 4.07 | 291.71M | 251/249 |

Quicksort | 2.67 | 241.81M | 164/206 |

Merge sort | 2.62 | 188.26M | 161/160 |

ASort | 1.62 | 117.34M | 100/100 |

Test Suite: 100M integers.

Sort algorithm | Seconds | Comparisons | Ratio % |

.NET sort | 46.36 | 3.39G | 261/255 |

Quicksort | 30.50 | 2.78G | 172/209 |

Merge sort | 29.36 | 2.12G | 165/160 |

ASort | 17.78 | 1.33G | 100/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).

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.

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.

The graph below shows the sorting algorithms and how their Θ(*n*log*n*) 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 Θ(*n*log*n*) as the number of elements increases.