O(n log n). I was very surprised to find out that, for sufficiently large number of items, the time it takes to sort
kfixed) is only
ktimes the time to sort
nitems. 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