Ninguno. Depende de las circunstancias.
Lógicamente, la siguiente pregunta es: ¿Cuál hay que usar en cada caso?
La mejor elección es casi siempre la implementación que viene incluida en el lenguaje que estás usando.
En algunos casos se puede elegir entre las siguientes opciones:
- Ordenación estable. Generalmente con memoria adicional O(N), es decir, proporcional a la ocupada por los datos a ordenar.
- Ordenación no estable. Requiere muy poca memoria adicional, pero no respeta el orden previo de los elementos que se consideran iguales entre sí.
Más detalles en: ordenación estable
y en: notación de la «O grande».
En C++, por ejemplo se puede elegir entre std::sort y std::stable_sort.
En el terreno de la ordenación con poca memoria adicional han destacado varios favoritos a lo largo de la historia: Shellsort (1959), quicksort (1960), heapsort (1964) y más recientemente introsort (1997), que es un híbrido de quicksort, heapsort y la ordenación por inserción.
Mergesort (1945) dominó muchos años en el terreno de la ordenación estable. Su sustituto parece ser Timsort (2002). Se trata también de un híbrido, en este caso de mergesort, la ordenación por inserción y algún truco más.
Hablaré de los pocos casos en los que sí tendría sentido (en mi opinión) usar un algoritmo de ordenación programado a medida. Pero será más adelante ;-)