How to sort nearly sorted array in the fastest time possible? (Java)

Question

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 be way faster than O(N)).

I know about smoothsort, but I can't find Java implementation. Does anyone know whether it is already implemented? Or what I can use for this task instead of smoothsort?

Answer 1

As Botz3000 noted, you can't perform such an operation faster than O(N). The most basic element of any algorithm would be to find those entries in the array that are out of order. This requires O(N), even before you figure out what to do with them.

If indeed the number of "out-of-order" elements is orders of magnitude below the total number of elements, you could use the following algorithm (assuming linked list):

1. Find all out-of-order items and extract the from the original list to a separate list, O(N)
2. The result is two lists: a sorted list and a short extracted list
3. For each of the extracted elements, insert them into the sorted list. That would be O(log(N)) for each, total is O(Xlog(N)), where X is the number of the extracted elements. If X is very small relative to N, you end up with a total of O(N).

Answer 2

Actualy, Wikipedia contains Java implementation of smoothsort: http://en.wikipedia.org/wiki/Smoothsort.

Answer 3

Cocktail Sort

If you want a simple algorithm that's easy to implement, you could do a cocktail sort. It would work reasonably well on nearly-sorted input.

Answer 4

You are right about the impossibility of reaching O(N), but assuming a multi-core machine (which I have), we can cheat a little by using a parallel sorting algorithm.

Answer 5

Implement what we called in school a Shell's sort. That's bubblesorting sub-arrays. A sub-array with step k is an array of elements with indicies 0, k, 2k, 3k...

If you choose k = 3i+1, and perform multiple bubble sorts, starting from higher i-s downto 0, the times will be smaller on nearly-sorted array.

Answer 6

[Sun] JDK7 has (or will have) an implementation of Tim sort (from Python). It's a merge sort that takes advantage of order already existing in the array.

Answer 7

Smoothsort or Timsort are great algorithms, and would be sensible things to use.

I'd add that what you might not realise is that the humble insertion sort is adaptive. Indeed, for really almost sorted lists, as you seem to have, my understanding (which i can't back up with a reference) is that it's faster than the more sophisticated algorithms. The problem is that if the input isn't almost-sorted, it rapidly degrades to O(n^2). Still, it's very simple to implement correctly, so if you know for sure that your input is always almost-sorted, it would be a good choice.