javaperformancealgorithmsortingsmoothsort

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

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?

Solution

  • Actually, the Wikipedia contains a Java implementation of smoothsort. You can find it here:

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