我有一个几乎是但不是很排序的值数组，有一些值被替换（例如，100000中有50个）。如何最有效地对其进行排序？（在这里，性能绝对至关重要，应该比O（N）更快）。

我了解Smoothsort，但是找不到Java实现。有谁知道它是否已经实施？或者我可以用什么代替平滑排序？