Какой тип использует Java Collections.sort(узлы)?

Я думаю, что это MergeSort, который является O (n log n).

Однако следующий вывод не согласуется:

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

Я сортирую нодлист из 4 узлов по порядковому номеру, и сортировка выполняет 6 сравнений. Я озадачен, потому что 6 > (4 log (4)). Может кто-нибудь объяснить это мне?

P.S. Это слияние, но я до сих пор не понимаю моих результатов.

Спасибо за ответы всем. Спасибо Том за исправление моей математики.

Ответ 1

O (n log n) не означает, что количество сравнений будет равно или меньше, чем n log n, так как это время будет масштабировать пропорционально n log n. Попробуйте выполнить тесты с 8 узлами или 16 узлами или 32 узлами и проверите время.

Ответ 2

Вы отсортировали четыре узла, поэтому вы не получили сортировку слияния; сортировка переключается на сортировку вставки.

В Java методы Arrays.sort() используют сортировку слияния или настроенную quicksort в зависимости от типов данных и эффективность реализации для сортировки вставки при сортировке менее семи элементов массива. ( Wikipedia, добавлено выделение)

Arrays.sort используется косвенно классами Collections.

Недавно принятый отчет об ошибке указывает, что реализация Sun Java будет использовать Python timsort в будущем: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124

(Монография timsort, связанная выше, стоит прочитать.)

Ответ 3

Алгоритм A (n), обрабатывающий количество данных n, находится в O (f (n)) для некоторой функции f, если существуют две строго положительные константы C_inf и C_sup такие, что:

C_inf. f (n) ExpectedValue (OperationCount (A (n))) < C_sup. е (п)

Следует отметить две вещи:

Фактические константы C могут быть любыми и зависят от относительной стоимости операций (в зависимости от языка, виртуальной машины, архитектуры или фактического определения операции). На некоторых платформах, например, + и * имеют одинаковую стоимость, на какой-то другой более поздний порядок на порядок медленнее.
Количество, обозначенное как "в O (f (n))", является ожидаемым количеством операций, основанным на некоторой, вероятно, произвольной модели данных, с которыми вы имеете дело. Например, если ваши данные почти полностью отсортированы, алгоритм сортировки слияния будет в основном O (n), а не O (n. Log (n)).

Ответ 4

Я написал кое-что, что вас может заинтересовать в алгоритме сортировки Java, и сделало некоторые измерения производительности Collections.sort(), Алгоритм в настоящее время представляет собой mergesort с сортировкой вставки, когда вы переходите к определенному размеру подсписок (NB, этот алгоритм, вероятно, изменится в Java 7).

Вы должны действительно взять ноту Big O как указание на то, как алгоритм будет масштабироваться в целом; для определенного вида точное время будет отклоняться от времени, предсказанного этим вычислением (как вы увидите на моем графике, два алгоритма сортировки, которые объединены, имеют разные характеристики производительности, и поэтому общее время для сортировки - это бит более сложный).

Тем не менее, в качестве приблизительного руководства, каждый раз, когда вы удваиваете количество элементов, если умножить ожидаемое время на 2.2, вы не будете далеко. (Это не имеет особого смысла делать это для очень маленьких списков нескольких элементов.)