sorting efficiently

I have an array of values which is almost, but not qui开发者_高级运维te sorted, with a few values displaced (say, 50 in 100000). How to sort it most efficiently?

Under the assumption that the array is almost sorted, you could use one of the following :

Smoothsort

Wiki even has a java implementation on it. Since you can't do it faster than O(n) (since it takes that much time in order to even find out if an array is sorted or not) smoothsort is a good choice. More details here.

The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree

Coctail sort

The complexity of cocktail sort in big O notation is O(n2) for both the worst case and the average case, but it becomes closer to O(n) if the list is mostly ordered before applying the sorting algorithm,

Timsort

Java's arrays are actually now using timsort in java 7 in order to sort objects (sort()). Description of timsort here.

Use insertion sort; it's great with almost-sorted arrays, since it's near O(n) time for them. I actually believe the .NET Framework uses insertion sort for sorting enum values internally (since they're often sorted), though I'd have to re-check that.

My first intuition would be to identify the misplaced elements and move them to a separate array, sort them there with whatever algorithm you like (with that few, it shouldn't matter), then merge sort them back in.

Finding the best algorithm for sorting depends on how much control you have over the data.

Sorting algorithms are classified into methods of insertion, exchange, selection, merging, etc.. This means that if you can control the mechanism that inserts new data on the array, you can sort them while doing that. If you can only sort the array after the data is there, then the best algorithm for doing that is another one completely different.

Anyway, these are interesting readings:

http://en.wikipedia.org/wiki/Sorting_algorithm

what-should-students-be-taught-first-when-first-learning-sorting-algorithms

comparison-of-sorting-algorithms

what-is-the-fastest-sorting-algorithm-in-c

Nowadays, the qsort or mergesort functions provided by most libc implementations already handle this special case in an efficient manner.

So, read your libc documentation or even better, check how it implements sorting (if you have access to the source), because sometimes this is an implementation detail not estated on the docs!