我有一个几乎是但不是很排序的值数组，有一些值被替换（例如，100000中有50个）。如何最有效地对其进行排序？（在这里，性能绝对至关重要，应该比O（N）更快）。
我了解Smoothsort，但是找不到Java实现。有谁知道它是否已经实施？或者我可以用什么代替平滑排序？
实际上，Wikipedia包含Smoothsort的Java实现。你可以在这里找到它：
http://en.wikipedia.org/wiki/Smoothsort。
