Si Arcadio necesita ordenar una lista de n números, no hay nada más sencillo que pedir ayuda a sus amigos. Pide a Úrsula que ordene una mitad de la lista, mientras que Luis ordena la otra. Cada uno le devuelve un papel con la parte de la lista ordenada y Arcadio, fácilmente, reúne ambas en una sola lista. Arcadio obtiene algoritmos diferentes, dependiendo de cómo decida dividir la lista. ¿Qué sucede si simplemente parte la lista a la mitad? Se obtiene el famoso algoritmo de ordenamiento por combinación (mergesort en inglés).
OrdenaM (L)
Si longitud de L es 1
Regresa L
De otro modo
Divide L en 2 del mismo tamaño (aproximadamente), L1 y L2
OrdenaM(L1)
OrdenaM(L2)
Mezcla(L1,L2)
Para finalizar, se describirá la subrutina de mezclado. El problema de mezclado consiste en combinar en una sola lista dos listas de números, cada una ordenada de la misma manera, de menor a mayor.
El tiempo de ejecución del algoritmo de ordenamiento por combinación, OrdenaM, es proporcional a n multiplicado por el logaritmo en base 2 de n, lo cual se denota como n log n. Esto es debido a que se tiene un árbol binario que representa el número de veces que se divide la lista en 2. Como se mencionó anteriormente, la altura del árbol es log n y el número de comparaciones por nivel es n, ejecutadas por el procedimiento de mezclado.
C. A. R. Hoare (1934)
C. A. R. Hoare (1934) Sir Charles Antony Richard Hoare recibió el PremioTuring en 1980 por sus contribuciones a los lenguajes de programación. Además, inventó QuickSort en 1960, que es el algoritmo de ordenamiento más utilizado en el mundo. Mientras era estudiante de intercambio en la Universidad Estatal de Moscú, le ofrecieron un puesto en el Laboratorio de Física Nacional en Teddington, para trabajar en un proyecto cuyo objetivo era traducir mecánicamente de ruso a inglés. Había la necesidad de ordenar todas las palabras en una oración, antes de poder localizarlas. Su primer intento le tomaba tiempo proporcional al cuadrado de la longitud de la oración, el segundo intento fue QuickSort. Sin embargo, tiempo después Hoare declinóel trabajo, porque la traducción mecánica de lenguajes naturales le pareció impráctica.
