Como el ordenamiento por mezcla, el ordenamiento rápido utiliza divide y vencerás, así que es un algoritmo recursivo. La manera en que el ordenamiento rápido utiliza divide y vencerás es un poco diferente de como lo hace el ordenamiento por mezcla. En el ordenamiento por mezcla, el paso de dividir casi no hace nada, y todo el trabajo real ocurre en el paso de combinar. El ordenamiento rápido es lo contrario: todo el trabajo real ocurre en el paso de dividir. De hecho, el paso de combinar en el ordenamiento rápido no hace absolutamente nada.
El ordenamiento rápido tiene un par de otras difrerencias con el ordenamiento por mezcla. El ordenamiento rápido trabaja in situ. Y el tiempo de ejecución de su peor caso es tan malo como el del ordenamiento por selección y el ordenamiento por inserción: Θ(n2) \Theta(n^2) . Pero el tiempo de ejecución de su caso promedio es tan bueno como el del ordenamiento por mezcla: Θ(nlgn) \Theta(n \lg n) . ¿Entonces por qué pensar acerca del ordenamiento rápido cuando el ordenamiento por mezcla es por lo menos igual de bueno? Eso es porque el factor constante escondido en la notación Θ grande para el ordenamiento rápido es bastante bueno. En la práctica, el ordenamiento rápido tiene un mejor desempeño que el ordenamiento por selección y tiene un desempeño significativamente mejor que el ordenamiento por inserción.
Aquí está cómo el ordenamiento rápido usa divide y vencerás. Como con el ordenamiento por mezcla, piensa en ordenar un subarreglo array[p..r], donde inicialmente el subarreglo es array[0..n-1].
  1. Divide al escoger cualquier elemento en el subarreglo array[p..r]. Llama a este elemento el pivote. Reacomoda los elementos en array[p..r] de modo que todos los demás elementos en array[p..r] que sean menores o iguales que el pivote estén a su izquierda y todos los demás elementos en array[p..r] estén a la derecha del pivote. A este procedimiento lo llamamos hacer una partición. En este punto, no importa qué orden tengan los elementos a la izquierda del pivote entre sí, y lo mismo ocurre para los elementos a la derecha del pivote. Solo nos importa que cada elemento esté en algún lugar del lado correcto del pivote.
    Como una cuestión práctica, siempre vamos a escoger el elemento de hasta la derecha en el subarreglo, array[r], como el pivote. Así que, por ejemplo, si el subarreglo consiste de [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], entonces escogemos 6 como el pivote. Después de hacer la partición, el subarreglo podría verse como [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Sea q el índice de dónde está el pivote.
  2. Vence al ordenar de manera recursiva los subarreglos array[p..q-1] (todos los elementos a la izquierda del pivote, los cuales deben ser menores o iguales que el pivote) y array[q+1..r] (todos los elementos a la derecha del pivote, los cuales deben ser mayores que el pivote).
  3. Combina al hacer nada. Una vez que el paso de conquistar ordena de manera recursiva, ya terminamos. ¿Por qué? Todos los elementos a la izquierda del pivote, en array[p..q-1], son menores o iguales que el pivote y están ordenados, y todos los elementos a la derecha del pivote, en array[q+1..r], son mayores que el pivote y están ordenados. ¡Los elementos en array[p..r] tienen que estar ordenados!
    Piensa acerca de nuestro ejemplo. Después de ordenar de manera recursiva los subarreglos a la izquierda y a la derecha del pivote, el subarreglo a la izquierda del pivote es [2, 3, 5], y el subarreglo a la derecha del pivote es [7, 9, 10, 11, 12, 14]. Así que el subarreglo tiene [2, 3, 5], seguido de 6, seguido de [7, 9, 10, 11, 12, 14]. El subarreglo está ordenado.
Los casos base son subarreglos con menos de dos elementos, justo como en el ordenamiento por mezcla. En el ordenamiento por mezcla nunca ves un subarreglo sin elementos, pero si puedes verlos en el ordenamiento rápido si los otros elementos en el subarreglo son todos menores que el pivote o son todos mayores que el pivote.
Volvamos al paso de vencer y recorramos el ordenamiento recursivo de los subarreglos. Después de hacer la primera partición tenemos los subarreglos [5, 2, 3] y [12, 7, 14, 9, 10, 11], con 6 como el pivote.
Para ordenar el subarreglo [5, 2, 3], escogemos a 3 como el pivote. Después de hacer la partición, tenemos [2, 3, 5]. El subarreglo [2], a la izquierda del pivote, es un caso base cuando hacemos recursividad, como lo es el subarreglo [5], a la derecha de pivote.
Para ordenar el subarreglo [12, 7, 14, 9, 10, 11], escogemos 11 como el pivote, que resulta en [7, 9, 10] a la izquierda del pivote y [14, 12] a la derecha. Después de que estos subarreglos están ordenados, tenemos [7, 9, 10], seguido de 11, seguido de [12, 14].
Aquí está cómo se desarrolla todo el algoritmo del ordenamiento rápido. Las ubicaciones de los arreglos en azul han sido pivotes en llamadas recursivas anteriores, así que los valores en estas ubicaciones no se van a volver a examinar o mover:
Ordenamiento rápido

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.