I have an array of values which is almost, but not quite sorted, with a few values displaced (say, 50 in 100000). How to sort it most efficiently? (performance is absolutely crucial here and should...

From reading this article from Wikipedia on sorting algorithms, it would seem that smoothsort is the best sorting algorithm there is. It has top performance in all categories: best, average, ...