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