Performance scaling of sorting algorithms

It is a well-known fact that the lowest theoretical bound on complexity of comparison-based sorting is O(n log n). I was very surprised to find out that, for sufficiently large number of items, the time it takes to sort k*n items (with k fixed) is only k times the time to sort n items. For deeper analysis you can have a look at this article.

So, it actually turns out that the approach of buying faster hardware can sometimes give expected performance gains.

Tags: Algorithms Sorting