¿Qué tipo utiliza Java Collections.sort (nodos)?

Creo que es MergeSort, que es O (n log n).

Sin embargo, el siguiente resultado no está de acuerdo:

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

Estoy ordenando una lista de nodos de 4 nodos por número de secuencia, y el género está haciendo 6 comparaciones. Estoy desconcertado porque 6> (4 log (4)). ¿Alguien me puede explicar esto?

PD Es mergesort, pero todavía no entiendo mis resultados.

Gracias por las respuestas a todos. Gracias Tom por corregir mis cálculos.

O (n log n) no significa que el número de comparaciones será igual o menor que n log n, solo que el tiempo tomado se escalará proporcionalmente a n log n. Intente hacer pruebas con 8 nodos, o 16 nodos, o 32 nodos, y revise el tiempo.

Ordenaste cuatro nodos, por lo que no obtuviste el tipo de combinación; ordenar cambiado a ordenar por inserción.

En Java, los métodos Arrays.sort () usan tipo de fusión o un recurso rápido sintonizado según los tipos de datos y para la eficiencia de la implementación cambian a ordenación por inserción cuando se ordenan menos de siete elementos del conjunto. (Wikipedia, énfasis agregado)

Arrays.sort es usado indirectamente por las clases de Colecciones.

Un informe de error recientemente aceptado indica que la implementación de Sun de Java utilizará el timsort de Python en el futuro: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124

(Vale la pena leer la monografía de timsort, vinculada anteriormente).

Un algoritmo A (n) que procesa una cantidad de datos n está en O (f (n)), para alguna función f, si existen dos constantes estrictamente positivas C_inf y C_sup tales que:

C_inf. f (n)

Dos cosas a tener en cuenta:

  • Las constantes reales C pueden ser cualquier cosa, y dependen de los costos relativos de las operaciones (según el idioma, la VM, la architecture o su definición real de una operación). En algunas plataformas, por ejemplo, + y * tienen el mismo costo, en otro el último es un orden de magnitud más lento.

  • La cantidad asignada como “en O (f (n))” es una cuenta de operación esperada , basada en algún modelo probablemente arbitrario de los datos con los que se está tratando. Por ejemplo, si sus datos están casi completamente ordenados, un algoritmo de clasificación de fusión va a ser principalmente O (n), no O (n. Log (n)).

He escrito algunas cosas que pueden interesarte sobre el algoritmo de ordenación de Java y he tomado algunas medidas de rendimiento de Collections.sort () . El algoritmo en este momento es un mergesort con un tipo de inserción una vez que se llega a un cierto tamaño de sublistas ( NB este algoritmo es muy probable que vaya a cambiar en Java 7 ).

Realmente debería tomar la notación Big O como una indicación de cómo el algoritmo se escalará en general; para un tipo particular, el tiempo preciso se desviará del tiempo predicho por este cálculo (como verá en mi gráfico, los dos algoritmos de ordenación que se combinan tienen características de rendimiento diferentes, por lo que el tiempo total para una clasificación es un poco más complejo).

Dicho eso, como una guía aproximada, por cada vez que duplicas la cantidad de elementos, si multiplicas el tiempo esperado por 2.2, no estarás lejos. (Sin embargo, no tiene mucho sentido hacer esto para listas muy pequeñas de algunos elementos).