Métodos de ordenamiento recursiva

Recursividad.
Es aquella propiedad que posee una función por el cual dicha función puede llamarse a sí misma.
Se puede utilizar como una alternativa a la iteración. Es una herramienta poderosa e importante en la resolución de problemas y en programación.

Una función es recursiva si es llamada a sí misma, directa o indirectamente a través de otra función g(). Es necesario contemplar un caso base o condición de salida, para dejar de hacer llamadas recursivas.
 

Una función tiene sentencias entre los cuales se encuentra al menos una que se llama a la propia  función se dice que es recursiva si se dispone de dos funciones F1 y F2,  la organización de un programa “no recursivo adoptara una forma similar a esto.”
 

8.2 Quick sort.
El ordenamiento rápido es un algoritmo recursivo basado en la técnica de divide y venceremos.
Elije un elemento de la lista al que llama pivote. Acomoda todos los elementos de la lista al lado del pivote, coloca a su izquierda todos los menores y a su derecha todos los mayores.

Entonces el pivote ya está en su posición.
Ahora hay 2 sub listas, una de menores y una de mayores, se repite de forma recursiva este proceso para cada sub lista.

Ventaja: Es rápido y no requiere memoria adicional.
 

Desventaja: Implementación poco complicada, recursividad (utiliza muchos recursos), Diferencia entre el mejor y el peor.