Legacy же
Диды квиксортили и правнуки будут

(Reply to this) (Thread)

Ну вот не надо.
В JDK, например, mergesort используется, на основе которого сделан timsort. Просто timsort заточен на типа real world задачи, в которых равномерно случайно распледеленные данные - скорее исключение.

(Reply to this) (Parent) (Thread)

Бля, начиная с OpenJDK 7 timsort штоле? Пиздец, а народ то и не в курсе.

(Reply to this) (Parent)

тим даже на полностью рандомных данных (ну, насколько их можно получить) показывает вполне годные результаты — лучше glibc-шного квиксорта. это очень странно, кстати: даже heap sort обходит qsort на таких наборах. по-моему, у меня поломаный тест.

(Reply to this) (Parent) (Thread)

Так что с тестами? Люди волнутся же, сколько можно саспенс этот держать?

(Reply to this) (Parent) (Thread)

да воьзми любую из реализаций и проверь. мне лень.

(Reply to this) (Parent) (Thread)

Хз, на полностью рандомизированных (на каждой итерации) данных квик все таки пизже, как и ожидалось:

# Warmup: 10 iterations, 1 s each
# Measurement: 10 iterations, 1 s each
# Benchmark mode: Average time, time/op

Benchmark            Mode  Cnt  Score   Error  Units
SortBench.mergeSort  avgt   20  0.436 ? 0.006  ms/op
SortBench.quickSort  avgt   20  0.206 ? 0.003  ms/op

(Reply to this) (Parent)

Бля, ты же там с хипсортом сравнивал. Плюс я в тесте проебался чучуть. Новые результаты:

Benchmark            Mode  Cnt  Score   Error  Units
SortBench.heapSort   avgt   20  1.503 ? 0.032  ms/op
SortBench.mergeSort  avgt   20  1.175 ? 0.026  ms/op
SortBench.quickSort  avgt   20  0.886 ? 0.010  ms/op

Сортировка написана одним и тем же человеком, соответственно радиус кривизны рук должен быть плюс-минус одинаков.

(Reply to this) (Parent)

О, а вот кстати jre-шный timsort. Как и было обещано, он не хуже mergesort'а на случайных данных:

SortBench.jreSort    avgt   20  1.048 ? 0.007  ms/op

(Reply to this) (Parent)