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

Question

Я думаю, что это 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.Это сортировка слиянием, но я до сих пор не понимаю своих результатов.

Спасибо за ответы всем.Спасибо, Том, что исправил мою математику.

Answer 1

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

Answer 2

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

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

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

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

(Монографию по тимсорту, ссылка на которую приведена выше, стоит прочитать.)

Answer 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).Лог(н)).

Answer 4

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

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

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