Mam tablicę wartości, która jest prawie, ale nie całkiem posortowana, z kilkoma wartościami przesuniętymi (powiedzmy 50 na 100000). Jak najlepiej sortować? (wydajność jest tutaj absolutnie kluczowa i powinna być szybsza niż O (N)).

Wiem o smoothsort, ale nie mogę znaleźć implementacji Java. Czy ktoś wie, czy jest już wdrożony? Lub co mogę użyć do tego zadania zamiast smoothsort?