Merge sort

La idea basica radica en el concepto de dividir y conquistar, que consiste en separar un problema grande en varios problemas pero mas chicos o faciles de resolver. Llevado al mundo del ordenamiento, el plan es el siguiente: dividi la lista a la mitad, y ordena cada mitad por separado. Una vez las tengas ordenadas, combinalas (merge, en inglés) ordenadamente. Lo bueno de este algoritmo, es que podemos plantearlo recursivamente, teniendo en cuenta que toda lista la podemos dividir a la mitad. Bueno, todas, salvo las de un unico elemento, pero esas ya estan ordenadas. Muy conveniente para un caso base.

flowchart TD

listaOriginal(6 2 9 5)
listaSplit1(6 2)
listaSplit2(9 5)
listaSplit3(6)
listaSplit4(2)
listaSplit5(9)
listaSplit6(5)
listaMerge1(2 6)
listaMerge2(5 9)
listaMerge3(2 5 6 9)

listaOriginal -->|split| listaSplit1
listaOriginal -->|split| listaSplit2

listaSplit1 -->|split| listaSplit3
listaSplit1 -->|split| listaSplit4

listaSplit2 -->|split| listaSplit5
listaSplit2 -->|split| listaSplit6

listaSplit3 -->|merge| listaMerge1
listaSplit4 -->|merge| listaMerge1

listaSplit5 -->|merge| listaMerge2
listaSplit6 -->|merge| listaMerge2

listaMerge1 -->|merge| listaMerge3
listaMerge2 -->|merge| listaMerge3

Si escribimos la formula en base a la idea recursiva del algoritmo, llegamos a que la complejidad del programa se puede escribir como:

T (n) = 2 T (\frac{n}{2} + O (n - 1))

Que por el teorema maestro, queda acotado a $O (n \log (n))$ .