Ordenación rápida Es un algoritmo interno que se basa en la estrategia de dividir y conquistar. En esto:

• La matriz de elementos se divide en partes repetidamente hasta que ya no es posible dividirla más.
• También se le conoce como clasificación de intercambio de partición .
• Utiliza un elemento clave (pivote) para particionar los elementos.
• Una partición izquierda contiene todos aquellos elementos que son más pequeños que el pivote y una partición derecha contiene todos aquellos elementos que son mayores que el elemento clave.

Combinar ordenar Es un algoritmo externo y se basa en la estrategia de dividir y conquistar. En esto:

• Los elementos se dividen en dos subconjuntos (n/2) una y otra vez hasta que solo queda un elemento.
• La ordenación por combinación utiliza almacenamiento adicional para ordenar la matriz auxiliar.
• La clasificación por combinación utiliza tres matrices, dos de las cuales se usan para almacenar cada mitad y la tercera externa se usa para almacenar la lista ordenada final fusionando otras dos y luego cada matriz se ordena de forma recursiva.
• Por último, todas las submatrices se fusionan para que el tamaño de elemento de la matriz sea 'n'.

Ordenación rápida versus ordenación por combinación

Partición de elementos en la matriz: en la ordenación por combinación, la matriz se divide en solo 2 mitades (es decir, n/2). mientras que en el caso de una clasificación rápida, la matriz se divide en cualquier proporción. No existe la obligación de dividir la matriz de elementos en partes iguales en una clasificación rápida. Peor de los casos de complejidad: el peor de los casos de complejidad de la clasificación rápida es O (n ^ 2), ya que se necesitan muchas comparaciones en las peores condiciones. mientras que en la clasificación por fusión, el peor de los casos y el caso promedio tienen las mismas complejidades O (n log n). Uso con conjuntos de datos: la clasificación por combinación puede funcionar bien en cualquier tipo de conjunto de datos, independientemente de su tamaño (ya sea grande o pequeño). mientras que la clasificación rápida no puede funcionar bien con grandes conjuntos de datos. Requisito de espacio de almacenamiento adicional: la clasificación por combinación no está implementada porque requiere espacio de memoria adicional para almacenar las matrices auxiliares. mientras que la clasificación rápida está disponible ya que no requiere ningún almacenamiento adicional. Eficiencia: la clasificación por combinación es más eficiente y funciona más rápido que la clasificación rápida en caso de conjuntos de datos o tamaños de matriz más grandes. mientras que la clasificación rápida es más eficiente y funciona más rápido que la clasificación por combinación en el caso de conjuntos de datos o tamaños de matriz más pequeños. Método de clasificación: la clasificación rápida es un método de clasificación interno en el que los datos se clasifican en la memoria principal. mientras que la clasificación por combinación es un método de clasificación externo en el que los datos que se van a clasificar no se pueden acomodar en la memoria y se necesita memoria auxiliar para clasificar. Estabilidad: la clasificación por combinación es estable ya que dos elementos con el mismo valor aparecen en el mismo orden en la salida ordenada que en la matriz de entrada sin clasificar. mientras que la clasificación rápida es inestable en este escenario. Pero se puede estabilizar mediante algunos cambios en el código. Preferido para: se prefiere la clasificación rápida para matrices. mientras que para listas vinculadas se prefiere la ordenación por combinación. Localidad de referencia: Quicksort exhibe una buena localidad de caché y esto hace que Quicksort sea más rápido que el ordenamiento por fusión (en muchos casos, como en el entorno de memoria virtual).