¿Por qué Quicksort es mejor que mergesort?

Me hicieron esta pregunta durante una entrevista. Ambos son O (nlogn) y, sin embargo, la mayoría de la gente usa Quicksort en lugar de Mergesort. ¿Porqué es eso?

Quicksort tiene O ( n 2 ) peor tiempo de ejecución y O ( n log n ) promedio de tiempo de ejecución de la caja. Sin embargo, es mejor fusionar el ordenamiento en muchos escenarios porque muchos factores influyen en el tiempo de ejecución de un algoritmo y, al tomarlos todos juntos, gana velocidad.

En particular, el tiempo de ejecución a menudo citado de los algoritmos de clasificación se refiere al número de comparaciones o la cantidad de intercambios necesarios para clasificar los datos. Esta es una buena medida de rendimiento, especialmente porque es independiente del diseño de hardware subyacente. Sin embargo, otras cosas, como la localidad de referencia (es decir, ¿leemos muchos elementos que probablemente estén en caché?), También juegan un papel importante en el hardware actual. Quicksort en particular requiere poco espacio adicional y exhibe una buena localidad de caché, y esto lo hace más rápido que el tipo de combinación en muchos casos.

Además, es muy fácil evitar el tiempo de ejecución del peor de los casos de la orden rápida de O ( n 2 ) casi por completo mediante el uso de una opción adecuada del pivote, como escoger al azar (esta es una estrategia excelente).

En la práctica, muchas implementaciones modernas de quicksort (en particular, std::sort libstdc ++) son en realidad introsort , cuyo peor caso teórico es O ( n log n ), al igual que merge sort. Esto se consigue limitando la profundidad de recursión y cambiando a un algoritmo diferente ( heapsort ) una vez que excede el log n .

Como mucha gente ha notado, el rendimiento promedio de casos para quicksort es más rápido que mergesort. Pero esto solo es cierto si está asumiendo un tiempo constante para acceder a cualquier parte de la memoria a pedido.

En RAM, esta suposición generalmente no es tan mala (no siempre es cierto debido a los cachés, pero no es tan malo). Sin embargo, si su estructura de datos es lo suficientemente grande como para vivir en el disco, entonces el quicksort se destruye por el hecho de que su disco promedio hace algo así como 200 búsquedas aleatorias por segundo. Pero ese mismo disco no tiene problemas para leer o escribir megabytes por segundo de datos secuencialmente. Que es exactamente lo que hace el mergesort.

Por lo tanto, si los datos deben ordenarse en el disco, realmente, realmente desea usar alguna variación en mergesort. (Por lo general, usted es una sublista de quicksort, y luego comienza a fusionarlas juntas por encima de cierto umbral de tamaño).

Además, si tiene que hacer algo con conjuntos de datos de ese tamaño, piense detenidamente cómo evitar búsquedas en el disco. Por ejemplo, esta es la razón por la cual es un consejo estándar que suelte los índices antes de hacer grandes cargas de datos en las bases de datos, y luego reconstruya el índice más tarde. Mantener el índice durante la carga significa buscar constantemente el disco. Por el contrario, si suelta los índices, la base de datos puede reconstruir el índice ordenando primero la información que se va a tratar (¡utilizando un mergesort por supuesto!) Y luego cargándola en una estructura de datos BTREE para el índice. (Los BTREE se mantienen naturalmente en orden, por lo que puede cargar uno desde un conjunto de datos ordenado con pocas búsquedas en disco).

Ha habido una serie de ocasiones en las que la comprensión de cómo evitar las búsquedas de discos me ha permitido hacer que los trabajos de procesamiento de datos tomen horas en lugar de días o semanas.

En realidad, QuickSort es O (n 2 ). El tiempo promedio de ejecución de su caso es O (nlog (n)), pero su peor caso es O (n 2 ), que ocurre cuando lo ejecuta en una lista que contiene pocos elementos únicos. La aleatorización toma O (n). Por supuesto, esto no cambia su peor caso, simplemente evita que un usuario malintencionado haga que su clasificación tarde mucho tiempo.

QuickSort es más popular porque:

  1. Está en el lugar (MergeSort requiere una memoria adicional lineal a la cantidad de elementos que se ordenarán).
  2. Tiene una pequeña constante oculta.

Los algoritmos de clasificación animados muestran una serie de algoritmos en 4 condiciones iniciales diferentes (aleatorio, casi ordenado, revertido, pocos únicos) y pueden ser útiles.

“y sin embargo, la mayoría de la gente usa Quicksort en lugar de Mergesort. ¿Por qué es eso?”

Una razón psicológica que no se ha dado es simplemente que Quicksort sea más inteligentemente nombrado. es decir, un buen marketing.

Sí, Quicksort con triple partición es probablemente uno de los mejores algoritmos de ordenación de propósito general, pero no se puede olvidar el hecho de que el género “Rápido” suena mucho más poderoso que el género “Fusionar”.

Como otros han notado, el peor caso de Quicksort es O (n ^ 2), mientras que mergesort y heapsort permanecen en O (nlogn). En el caso promedio, sin embargo, los tres son O (nlogn); por lo que son para la gran mayoría de los casos comparables.

Lo que hace que Quicksort sea mejor en promedio es que el ciclo interno implica comparar varios valores con uno solo, mientras que en los otros dos, ambos términos son diferentes para cada comparación. En otras palabras, Quicksort realiza la mitad de lecturas que los otros dos algoritmos. En los CPU modernos, el rendimiento está fuertemente dominado por los tiempos de acceso, por lo que al final Quicksort termina siendo una gran primera opción.

Me gustaría agregar que de los tres algoritmos mencionados hasta ahora (mergesort, quicksort y heap sort) solo mergesort es estable. Es decir, el orden no cambia para aquellos valores que tienen la misma clave. En algunos casos, esto es deseable.

Pero, a decir verdad, en situaciones prácticas la mayoría de las personas solo necesita un buen rendimiento promedio y el quicksort es … rápido =)

Todos los algoritmos de ordenamiento tienen sus altibajos. Vea el artículo de Wikipedia para los algoritmos de clasificación para una buena descripción general.

Mu! Quicksort no es mejor, es adecuado para un tipo diferente de aplicación, que mergesort.

Mergesort vale la pena considerar si la velocidad es esencial, no se puede tolerar el peor rendimiento en el peor de los casos y hay más espacio disponible. 1

Usted declaró que ellos “Ambos son O (nlogn) […]”. Esto está mal. «Quicksort utiliza aproximadamente n ^ 2/2 comparaciones en el peor de los casos.» 1 .

Sin embargo, la propiedad más importante de acuerdo con mi experiencia es la fácil implementación del acceso secuencial que puede usar al ordenar cuando usa lenguajes de progtwigción con el paradigma imperativo.

1 Sedgewick, Algoritmos

Quicksort es el algoritmo de clasificación más rápido en la práctica, pero tiene una serie de casos patológicos que pueden hacer que funcione tan mal como O (n2).

Se garantiza que Heapsort se ejecutará en O (n * ln (n)) y solo requiere un almacenamiento adicional finito. Pero hay muchas citas de pruebas del mundo real que muestran que el heapsort es significativamente más lento que el quicksort en promedio.

De la entrada de Wikipedia en Quicksort :

Quicksort también compite con mergesort, otro algoritmo de ordenamiento recursivo, pero con el beneficio del peor tiempo de ejecución de Θ (nlogn). Mergesort es un tipo estable, a diferencia de quicksort y heapsort, y se puede adaptar fácilmente para operar en listas vinculadas y listas muy grandes almacenadas en medios de acceso lento como el almacenamiento en disco o el almacenamiento conectado a la red. Aunque se puede escribir en el quicksort para operar en listas vinculadas, a menudo sufrirá malas elecciones de pivote sin acceso aleatorio. La principal desventaja de mergesort es que, cuando se opera en matrices, requiere Θ (n) espacio auxiliar en el mejor de los casos, mientras que la variante de quicksort con partición en contexto y recursión de cola usa solo Θ (logn) espacio. (Tenga en cuenta que cuando se opera en listas enlazadas, mergesort solo requiere una cantidad pequeña y constante de almacenamiento auxiliar).

La explicación de Wikipedia es:

Típicamente, quicksort es significativamente más rápido en la práctica que otros algoritmos Θ (nlogn), porque su bucle interno se puede implementar eficientemente en la mayoría de las architectures, y en la mayoría de los datos del mundo real es posible tomar decisiones de diseño que minimicen la probabilidad de requerir un tiempo cuadrático .

Ordenación rápida

Mergesort

Creo que también hay problemas con la cantidad de almacenamiento necesario para Mergesort (que es Ω (n)) que las implementaciones de la solución rápida no tienen. En el peor de los casos, tienen la misma cantidad de tiempo algorítmico, pero mergesort requiere más almacenamiento.

Quicksort NO es mejor que mergesort. Con O (n ^ 2) (el peor caso que rara vez ocurre), el orden rápido es potencialmente mucho más lento que el O (nlogn) del tipo de fusión. Quicksort tiene menos sobrecarga, por lo que con pequeñas computadoras n y lentas, es mejor. Pero las computadoras son tan rápidas hoy en día que la sobrecarga adicional de un mergesort es insignificante, y el riesgo de una conexión rápida muy lenta supera con creces la carga general insignificante de un mergesort en la mayoría de los casos.

Además, un mergesort deja elementos con claves idénticas en su orden original, un atributo útil.

Me gustaría agregar a las grandes respuestas existentes algunas matemáticas sobre cómo funciona QuickSort al divergir del mejor de los casos y qué tan probable es, lo que espero ayude a las personas a entender un poco mejor por qué el caso O (n ^ 2) no es real preocupación en las implementaciones más sofisticadas de QuickSort.

Fuera de los problemas de acceso aleatorio, hay dos factores principales que pueden afectar el rendimiento de QuickSort y ambos están relacionados con la forma en que el pivote se compara con los datos que se ordenan.

1) Un pequeño número de claves en los datos. Un conjunto de datos de todo el mismo valor se ordenará en n ^ 2 veces en una clasificación rápida de 2 particiones porque todos los valores, excepto la ubicación de pivote, se colocan en un lado cada vez. Las implementaciones modernas abordan esto mediante métodos como el uso de una clasificación de 3 particiones. Estos métodos se ejecutan en un conjunto de datos de todo el mismo valor en O (n) tiempo. Por lo tanto, el uso de dicha implementación significa que una entrada con un número pequeño de claves en realidad mejora el tiempo de rendimiento y ya no es una preocupación.

2) La selección de pivote extremadamente mala puede causar el peor de los casos. En un caso ideal, el pivote siempre será tal que el 50% de los datos sean más pequeños y el 50% de los datos sean más grandes, de modo que la entrada se dividirá por la mitad durante cada iteración. Esto nos da n comparaciones y swaps por log-2 (n) recursiones para el tiempo O (n * logn).

¿Cuánto afecta la selección de pivote no ideal al tiempo de ejecución?

Consideremos un caso en el que el pivote se elige de forma consistente, de forma que el 75% de los datos esté en un lado del pivote. Sigue siendo O (n * logn) pero ahora la base del registro ha cambiado a 1 / 0.75 o 1.33. La relación de rendimiento al cambiar de base siempre es una constante representada por log (2) / log (newBase). En este caso, esa constante es 2.4. Por lo tanto, esta calidad de elección de pivote demora 2.4 veces más que la ideal.

¿Qué tan rápido empeora esto?

No es muy rápido hasta que la opción pivote se vuelve (consistentemente) muy mala:

  • 50% en un lado: (caso ideal)
  • 75% en un lado: 2.4 veces más largo
  • 90% en un lado: 6.6 veces más largo
  • 95% en un lado: 13.5 veces más largo
  • 99% en un lado: 69 veces más largo

Cuando nos acercamos al 100% de un lado, la porción de registro de la ejecución se acerca a ny toda la ejecución se aproxima asintóticamente a O (n ^ 2).

En una implementación ingenua de QuickSort, casos como una matriz ordenada (para el pivote del primer elemento) o una matriz ordenada inversamente (para el pivote del último elemento) producirán de manera fiable el peor tiempo de ejecución O (n ^ 2). Además, las implementaciones con una selección de pivote predecible pueden someterse al ataque DoS por datos diseñados para producir la peor ejecución de caso. Las implementaciones modernas evitan esto mediante una variedad de métodos, como aleatorizar los datos antes de ordenar, elegir la mediana de 3 índices elegidos al azar, etc. Con esta aleatorización en la mezcla, tenemos 2 casos:

  • Pequeño conjunto de datos. El peor caso es razonablemente posible, pero O (n ^ 2) no es catastrófico porque n es lo suficientemente pequeño como para que n ^ 2 también sea pequeño.
  • Gran conjunto de datos. El peor caso es posible en teoría, pero no en la práctica.

¿Qué tan probable es que veamos un rendimiento terrible?

Las posibilidades son infinitamente pequeñas . Consideremos un tipo de 5,000 valores:

Nuestra implementación hipotética elegirá un pivote utilizando una mediana de 3 índices elegidos al azar. Consideraremos que los pivotes que están en el rango de 25% -75% son “buenos” y los pivotes que están en el rango de 0% -25% o 75% -100% son “malos”. Si nos fijamos en la distribución de probabilidad utilizando la mediana de 3 índices aleatorios, cada recursión tiene una probabilidad de 11/16 de terminar con un buen pivote. Hagamos 2 suposiciones conservadoras (y falsas) para simplificar las matemáticas:

  1. Los buenos pivotes están siempre exactamente en una división de 25% / 75% y operan en 2.4 * caso ideal. Nunca conseguimos una división ideal o una división mejor que 25/75.

  2. Los malos pivotes siempre son el peor de los casos y esencialmente no contribuyen en nada a la solución.

Nuestra implementación de QuickSort se detendrá en n = 10 y cambiará a una ordenación de inserción, por lo que requerimos 22 particiones pivotantes 25% / 75% para romper la entrada de valor 5,000 hasta ese momento. (10 * 1.333333 ^ 22> 5000) O bien, requerimos 4990 pivotes en el peor de los casos. Tenga en cuenta que si acumulamos 22 pivotes buenos en algún punto, entonces el tipo se completará, por lo que el peor de los casos o cualquier cosa cerca de él requiere una muy mala suerte. Si nos tomó 88 recursiones para lograr realmente los 22 buenos pivotes requeridos para clasificar a n = 10, eso sería 4 * 2.4 * caso ideal o aproximadamente 10 veces el tiempo de ejecución del caso ideal. ¿Cuán probable es que no logremos los 22 pivotes buenos requeridos después de las 88 repeticiones?

Las distribuciones de probabilidad binomial pueden responder eso, y la respuesta es aproximadamente 10 ^ -18. (n es 88, k es 21, p es 0.6875) Su usuario tiene una probabilidad mil veces mayor de ser alcanzado por un rayo en el lapso de 1 segundo que tarda en hacer clic en [ORDENAR] que en ver que el orden de los 5.000 elementos empeora de 10 * caso ideal. Esta oportunidad se reduce a medida que el conjunto de datos se hace más grande. Aquí hay algunos tamaños de matriz y sus correspondientes oportunidades de ejecutar más de 10 * ideal:

  • Matriz de 640 elementos: 10 ^ -13 (requiere 15 buenos puntos de pivote de 60 bashs)
  • Matriz de 5.000 elementos: 10 ^ -18 (requiere 22 buenos pivotes de 88 bashs)
  • Matriz de 40,000 artículos: 10 ^ -23 (requiere 29 buenos pivotes de 116)

Recuerde que esto es con 2 suposiciones conservadoras que son peores que la realidad. Así que el rendimiento real es mejor aún, y el rest de la probabilidad restante está más cerca del ideal que no.

Finalmente, como han mencionado otros, incluso estos casos absurdamente improbables pueden eliminarse cambiando a un tipo de montón si la stack de recursión es demasiado profunda. Entonces, el TLDR es que, para una buena implementación de QuickSort, el peor de los casos no existe realmente porque ha sido diseñado y la ejecución se completa en el tiempo O (n * logn).

La respuesta se inclinaría ligeramente hacia quicksort wrt a los cambios traídos con DualPivotQuickSort para valores primitivos. Se usa en JAVA 7 para ordenar en java.util.Arrays

 It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. Full mathematical proof see in attached proof.txt and proof_add.txt files. Theoretical results are also confirmed by experimental counting of the operations. 

Puede encontrar la implementación de JAVA7 aquí – http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Lectura adicional impresionante en DualPivotQuickSort – http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Si bien ambos están en la misma clase de complejidad, eso no significa que ambos tengan el mismo tiempo de ejecución. Quicksort suele ser más rápido que mergesort, simplemente porque es más fácil codificar una implementación ajustada y las operaciones que realiza pueden ir más rápido. Es porque ese quicksort generalmente es más rápido que las personas lo usan en lugar de mergesort.

¡Sin embargo! Personalmente, a menudo usaré mergesort o una variante de quicksort que se degrada a mergesort cuando quicksort lo hace mal. Recuerda. Quicksort es solo O (n log n) en promedio . ¡Lo peor es O (n ^ 2)! Mergesort siempre es O (n log n). En los casos en los que el rendimiento en tiempo real o la capacidad de respuesta es una necesidad y sus datos de entrada podrían provenir de una fuente maliciosa, no debe usar la ordenación simple.

Quicksort tiene una mejor complejidad media de casos, pero en algunas aplicaciones es la opción incorrecta. Quicksort es vulnerable a los ataques de denegación de servicio. Si un atacante puede elegir la entrada que se ordenará, puede construir fácilmente un conjunto que tome la peor complejidad de tiempo de caso de o (n ^ 2).

La complejidad promedio de casos de Mergesort y la complejidad del peor caso son las mismas, y como tal no sufre el mismo problema. Esta propiedad de merge-sort también la convierte en la mejor opción para los sistemas en tiempo real, precisamente porque no hay casos patológicos que hagan que se ejecute mucho, mucho más despacio.

Soy fan de Mergesort más que de Quicksort por estos motivos.

En igualdad de condiciones, esperaría que la mayoría de las personas usen lo que sea más conveniente, y eso tiende a ser qsort (3). Aparte de que se conoce que quicksort es muy rápido en las matrices, al igual que mergesort es la opción común para las listas.

Lo que me pregunto es por qué es tan raro ver el tipo de raíz o cubo. Son O (n), al menos en listas vinculadas y todo lo que necesita es algún método para convertir la clave en un número ordinal. (Cuerdas y flotadores funcionan bien)

Estoy pensando que la razón tiene que ver con cómo se enseña la informática. Incluso tuve que demostrar a mi profesor en el análisis de algoritmos que, de hecho, era posible ordenar más rápido que O (n log (n)). (Tenía la prueba de que no se puede comparar el género más rápido que O (n log (n)), lo cual es cierto).

En otras noticias, los flotadores se pueden ordenar como enteros, pero luego debes girar los números negativos.

Editar: En realidad, aquí hay una forma aún más viciosa de ordenar flotantes como enteros: http://www.stereopsis.com/radix.html . Tenga en cuenta que el truco de inversión de bits se puede usar independientemente del algoritmo de ordenación que utilice realmente …

Eso es difícil de decir. Lo peor de MergeSort es n (log2n) -n + 1, que es preciso si n es igual a 2 ^ k (ya lo he demostrado). Y para cualquier n, está entre (n lg n – n + 1) y (n lg n + n + O (lg n)). Pero para quickSort, su mejor es nlog2n (también n es igual a 2 ^ k). Si divide Mergesort por quickSort, es igual a uno cuando n es infinito. es como si el peor caso de MergeSort fuera mejor que el mejor caso de QuickSort, ¿por qué usamos quicksort? Pero recuerde, MergeSort no está en su lugar, requiere 2n memeroy espacio. Y MergeSort también necesita hacer muchas copias de matriz, que no incluir en el análisis de algoritmo.En una palabra, MergeSort es realmente más rápido que quicksort en theroy, pero en realidad necesita considerar el espacio de memeory, el costo de la copia de array, la fusión es más lenta que la ordenación rápida. Una vez hice un experimento donde me dieron 1000000 dígitos en Java por clase aleatoria, y tomó 2610ms por mergesort, 1370ms por quicksort.

¿Por qué Quicksort es bueno?

  • QuickSort toma N ^ 2 en el peor de los casos y NlogN average case. El peor caso ocurre cuando los datos están ordenados. Esto se puede mitigar aleatoriamente antes de comenzar la clasificación.
  • QuickSort no toma memoria extra que se toma por tipo de fusión.
  • Si el conjunto de datos es grande y hay elementos idénticos, la complejidad de Quicksort se reduce al utilizar una partición de 3 vías. Más el no de artículos idénticos mejora el género. Si todos los elementos son idénticos, se ordena en tiempo lineal. [Esta es la implementación predeterminada en la mayoría de las bibliotecas]

¿Quicksort siempre es mejor que Mergesort?

Realmente no.

  • Mergesort es estable pero Quicksort no lo es. Entonces, si necesita estabilidad en la salida, usaría Mergesort. Se requiere estabilidad en muchas aplicaciones prácticas.
  • La memoria es barata hoy en día. Entonces, si la memoria extra utilizada por Mergesort no es crítica para su aplicación, no hay ningún daño al usar Mergesort.

Nota: En Java, la función Arrays.sort () usa Quicksort para tipos de datos primitivos y Mergesort para tipos de datos de objetos. Debido a que los objetos consumen una sobrecarga de memoria, por lo que agregar un poco de sobrecarga para Mergesort puede no ser un problema para el punto de vista del rendimiento.

Referencia : Vea los videos QuickSort de la Semana 3, Curso de Algoritmos de Princeton en Coursera

La ordenación rápida es el caso más desfavorable O (n ^ 2), sin embargo, el caso promedio siempre supera el tipo de fusión. Cada algoritmo es O (nlogn), pero debe recordar que cuando hablamos de Big O dejamos fuera los factores de complejidad más bajos. La ordenación rápida tiene mejoras significativas sobre el tipo de fusión cuando se trata de factores constantes.

La clasificación por fusión también requiere memoria O (2n), mientras que la ordenación rápida se puede realizar en su lugar (solo requiere O (n)). Esta es otra razón por la que generalmente se prefiere el ordenamiento rápido sobre el tipo de fusión.

Información extra:

El peor caso de clasificación rápida ocurre cuando el pivote está mal elegido. Considere el siguiente ejemplo:

[5, 4, 3, 2, 1]

Si el pivote se elige como el número más pequeño o más grande en el grupo, la ordenación rápida se ejecutará en O (n ^ 2). La probabilidad de elegir el elemento que está en el 25% más grande o más pequeño de la lista es 0.5. Eso le da al algoritmo una probabilidad de 0.5 de ser un buen pivote. Si empleamos un algoritmo de elección de pivote típico (por ejemplo, elegir un elemento aleatorio), tenemos 0.5 posibilidades de elegir un buen pivote para cada opción de un pivote. Para colecciones de gran tamaño, la probabilidad de elegir siempre un pivote pobre es 0.5 * n. Con base en esta probabilidad, el ordenamiento rápido es eficiente para el caso promedio (y típico).

En merge-sort, el algoritmo general es:

  1. Ordenar la sub-matriz izquierda
  2. Ordenar la sub-matriz correcta
  3. Combina las 2 sub-matrices ordenadas

En el nivel superior, fusionar las 2 sub-matrices ordenadas implica lidiar con N elementos.

Un nivel por debajo de eso, cada iteración del paso 3 implica tratar con N / 2 elementos, pero debe repetir este proceso dos veces. Entonces todavía estás tratando con 2 * N / 2 == N elementos.

Un nivel debajo de eso, está fusionando 4 * N / 4 == N elementos, y así sucesivamente. Cada profundidad en la stack recursiva implica fusionar la misma cantidad de elementos en todas las llamadas para esa profundidad.

Considere el algoritmo de ordenación rápida en su lugar:

  1. Elige un punto de pivote
  2. Coloque el punto de pivote en el lugar correcto de la matriz, con todos los elementos más pequeños a la izquierda y los elementos más grandes a la derecha
  3. Ordenar el sub-grupo izquierdo
  4. Ordenar el sub-grupo correcto

En el nivel superior, se trata de una matriz de tamaño N. A continuación, elige un punto de pivote, lo coloca en su posición correcta y puede ignorarlo por completo durante el rest del algoritmo.

Un nivel por debajo de eso, se trata de 2 sub-arrays que tienen un tamaño combinado de N-1 (es decir, restan el punto de pivote anterior). Usted elige un punto de pivote para cada sub-matriz, que llega a 2 puntos de pivote adicionales.

One level below that, you’re dealing with 4 sub-arrays with combined size N-3, for the same reasons as above.

Then N-7… Then N-15… Then N-32…

The depth of your recursive stack remains approximately the same (logN). With merge-sort, you’re always dealing with a N-element merge, across each level of the recursive stack. With quick-sort though, the number of elements that you’re dealing with diminishes as you go down the stack. For example, if you look at the depth midway through the recursive stack, the number of elements you’re dealing with is N – 2^((logN)/2)) == N – sqrt(N).

Disclaimer: On merge-sort, because you divide the array into 2 exactly equal chunks each time, the recursive depth is exactly logN. On quick-sort, because your pivot point is unlikely to be exactly in the middle of the array, the depth of your recursive stack may be slightly greater than logN. I haven’t done the math to see how big a role this factor and the factor described above, actually play in the algorithm’s complexity.

When I experimented with both sorting algorithms, by counting the number of recursive calls, quicksort consistently has less recursive calls than mergesort. It is because quicksort has pivots, and pivots are not included in the next recursive calls. That way quicksort can reach recursive base case more quicker than mergesort.

Unlike Merge Sort Quick Sort doesn’t uses an auxilary space. Whereas Merge Sort uses an auxilary space O(n). But Merge Sort has the worst case time complexity of O(nlogn) whereas the worst case complexity of Quick Sort is O(n^2) which happens when the array is already is sorted.

Small additions to quick vs merge sorts.

Also it can depend on kind of sorting items. If access to items, swap and comparisons is not simple operations, like comparing integers in plane memory, then merge sort can be preferable algorithm.

For example , we sort items using network protocol on remote server.

Also, in custom containers like “linked list”, the are no benefit of quick sort.
1. Merge sort on linked list, don’t need additional memory. 2. Access to elements in quick sort is not sequential (in memory)

Something to consider is memory as well. Mergesort requires an additional array, say a “workspace array”. If your memory is barely big enough to store your original array, then mergesort will not work.

Quick sort is an in-place sorting algorithm, so its better suited for arrays. Merge sort on the other hand requires extra storage of O(N), and is more suitable for linked lists.

Unlike arrays, in liked list we can insert items in the middle with O(1) space and O(1) time, therefore the merge operation in merge sort can be implemented without any extra space. However, allocating and de-allocating extra space for arrays have an adverse effect on the run time of merge sort. Merge sort also favors linked list as data is accessed sequentially, without much random memory access.

Quick sort on the other hand requires a lot of random memory access and with an array we can directly access the memory without any traversing as required by linked lists. Also quick sort when used for arrays have a good locality of reference as arrays are stored contiguously in memory.

Even though both sorting algorithms average complexity is O(NlogN), usually people for ordinary tasks uses an array for storage, and for that reason quick sort should be the algorithm of choice.

EDIT: I just found out that merge sort worst/best/avg case is always nlogn, but quick sort can vary from n2(worst case when elements are already sorted) to nlogn(avg/best case when pivot always divides the array in two halves).

This is a pretty old question, but since I’ve dealt with both recently here are my 2c:

Merge sort needs on average ~ N log N comparisons. For already (almost) sorted sorted arrays this gets down to 1/2 N log N, since while merging we (almost) always select “left” part 1/2 N of times and then just copy right 1/2 N elements. Additionally I can speculate that already sorted input makes processor’s branch predictor shine but guessing almost all branches correctly, thus preventing pipeline stalls.

Quick sort on average requires ~ 1.38 N log N comparisons. It does not benefit greatly from already sorted array in terms of comparisons (however it does in terms of swaps and probably in terms of branch predictions inside CPU).

My benchmarks on fairly modern processor shows the following:

When comparison function is a callback function (like in qsort() libc implementation) quicksort is slower than mergesort by 15% on random input and 30% for already sorted array for 64 bit integers.

On the other hand if comparison is not a callback, my experience is that quicksort outperforms mergesort by up to 25%.

However if your (large) array has a very few unique values, merge sort starts gaining over quicksort in any case.

So maybe the bottom line is: if comparison is expensive (eg callback function, comparing strings, comparing many parts of a structure mostly getting to a second-third-forth “if” to make difference) – the chances are that you will be better with merge sort. For simpler tasks quicksort will be faster.

That said all previously said is true: – Quicksort can be N^2, but Sedgewick claims that a good randomized implementation has more chances of a computer performing sort to be struck by a lightning than to go N^2 – Mergesort requires extra space

In c/c++ land, when not using stl containers, I tend to use quicksort, because it is built into the run time, while mergesort is not.

So I believe that in many cases, it is simply the path of least resistance.

In addition performance can be much higher with quick sort, for cases where the entire dataset does not fit into the working set.

One of the reason is more philosophical. Quicksort is Top->Down philosophy. With n elements to sort, there are n! possibilities. With 2 partitions of m & nm which are mutually exclusive, the number of possibilities go down in several orders of magnitude. ¡metro! * (nm)! is smaller by several orders than n! alone. imagine 5! vs 3! *2!. 5! has 10 times more possibilities than 2 partitions of 2 & 3 each . and extrapolate to 1 million factorial vs 900K!*100K! vs. So instead of worrying about establishing any order within a range or a partition,just establish order at a broader level in partitions and reduce the possibilities within a partition. Any order established earlier within a range will be disturbed later if the partitions themselves are not mutually exclusive.

Any bottom up order approach like merge sort or heap sort is like a workers or employee’s approach where one starts comparing at a microscopic level early. But this order is bound to be lost as soon as an element in between them is found later on. These approaches are very stable & extremely predictable but do a certain amount of extra work.

Quick Sort is like Managerial approach where one is not initially concerned about any order , only about meeting a broad criterion with No regard for order. Then the partitions are narrowed until you get a sorted set. The real challenge in Quicksort is in finding a partition or criterion in the dark when you know nothing about the elements to sort. That is why we either need to spend some effort to find a median value or pick 1 at random or some arbitrary “Managerial” approach . To find a perfect median can take significant amount of effort and leads to a stupid bottom up approach again. So Quicksort says just a pick a random pivot and hope that it will be somewhere in the middle or do some work to find median of 3 , 5 or something more to find a better median but do not plan to be perfect & don’t waste any time in initially ordering. That seems to do well if you are lucky or sometimes degrades to n^2 when you don’t get a median but just take a chance. Any way data is random. derecho. So I agree more with the top ->down logical approach of quicksort & it turns out that the chance it takes about pivot selection & comparisons that it saves earlier seems to work better more times than any meticulous & thorough stable bottom ->up approach like merge sort. Pero