¿Por qué Merge sort se utiliza para objetos en Android / Java API?

En Java Arrays.sort () para tipos primitivos utiliza ordenación rápida. Por otro lado, Arrays.sort () para objetos utiliza la clase Merge. Y, lo mismo ocurre con Collection.sort () que también utiliza Merge sort. Las colecciones de ordenación utilizan la implementación de ordenación Arrays debajo. Por lo tanto, en un sentido simple puedo decir que las primitivas se ordenan mediante ordenación rápida, pero los objetos se ordenan mediante la ordenación de mezcla.

Mi suposición es que tiene algo que ver con el algoritmo de clasificación de sí mismo. Hay tantas discusiones sobre SO en la clasificación rápida vs Merge sort, como esto y esto . Parece ser que hay afirmaciones contradictorias sobre las cuales uno es mejor, lo cual es comprensible ya que esto depende de conjuntos de datos.

Mi entendimiento es

En el lugar: Triunfos rápidos. El tipo de combinación se puede implementar in-place para la lista enlazada
Datos de almacenamiento externo: triunfos de clasificación de combinación.
Lista de clasificación (respaldada por cualquier forma de lista vinculada): Merge sort wins. Enlazar

Android API parece seguir el mismo patrón que Java. Esto es lo que encontré en Arrays.java

public static void sort(long[] array) { DualPivotQuicksort.sort(array); }

Y esto,

 public static void sort(Object[] array) { ComparableTimSort.sort(array); }

Lo que no entiendo es, ¿qué hace que Merge clasifique un buen candidato para ordenar objetos en Java o en Android? ¿Por qué no dejar esta decisión a los desarrolladores?

La cuestión clave es la estabilidad de ordenación: si dos elementos son iguales desde el punto de vista del orden, aparecen en el resultado en el mismo orden que en la entrada.

No importa por ejemplo long . Todas las instancias de 3 en la entrada se agruparán, y nadie se preocupa por cuál.

Por otro lado, los objetos pueden diferir en formas que no afectan al orden. Si está ordenando a los animales por el número de patas, puede importar si "gato" y "perro" permanecen en el orden original o no.

El fusible de Arrays.sort es estable. El quicksort utilizado para las primitivas no necesita ser estable.

Por favor, vea esta respuesta: ¿Por qué Collections.sort utiliza el tipo de combinación en lugar de quicksort?

TL, DR:

QuickSort tiene dos deficiencias importantes en comparación con mergesort:

No es estable (como lo observó parsifal).

No garantiza el rendimiento n log n; Puede degradarse al rendimiento cuadrático en insumos patológicos.

Creo que la cuestión de

Lo que hace que el tipo de fusión sea un buen candidato para ordenar objetos Java y ordenar rápidamente los primitivos?

Ha sido contestada por otros, pero la cuestión de

¿Por qué esta decisión no ha sido dejada a los desarrolladores?

Aún no se ha abordado.

El hecho es que cualquier desarrollador puede derivar fácilmente una nueva clase de Collection o ArrayList y ocultar el método sort() ya que sort() es un método static que debe estar oculto, no oculto ) y usar su propia implementación personalizada.

El hecho de que esto rara vez (si alguna vez) es hecho quizás porque la mayoría de los programadores jóvenes de hoy han tenido más exposición a Java que a C ++. En la comunidad de Java, la "abstracción" se toma para significar que usted no tiene ninguna idea de cómo la puesta en práctica subyacente de una clase trabaja realmente, y además, que usted no necesita. La independencia de la máquina de la JVM ha arruinado nuestra intuición de los compromisos de velocidad / eficiencia. Como resultado, muchos de nosotros no tenemos una comprensión tan clara de las estructuras de datos y algoritmos como algunos de los programadores más antiguos y más experimentados.

Esto es casi lo opuesto a la comprensión de la abstracción en C ++. Para citar a Alex Stepanov:

De hecho, no creo que una biblioteca podría eliminar la necesidad de un programador para conocer algoritmos y estructuras de datos. Sólo elimina la necesidad de un programador para implementarlos. Es necesario comprender las propiedades fundamentales de las estructuras de datos para utilizarlas adecuadamente de modo que la aplicación satisfaga sus propios requisitos de complejidad.

El tipo de combinación es estable: los elementos iguales no se reordenarán como resultado del tipo