Estrategia de Merge Sort

Estrategia de Merge Sort
Merge Sort está basado en la técnica de diseño de algoritmos Divide y Vencerás, de la cual se habló aquí mismo hace un tiempo. Recordando un poco, esta técina consiste endividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente  pequeños o triviales.

Veamos una panorámica de la estrategia que sigue estealgoritmo para ordenar una secuencia S de n elementos:
Si S tiene uno o ningún elemento, está ordenada
Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2
S1 contiene los primeros n/2elementos y S2 los restantes
Ordenar S1 y S2, aplicando recursivamente este procedimiento
Mezclar S1 y S2 en S, de forma que ya S1 y S2 estén ordenados
Veamos ahora como sería la estrategia paramezclar las secuencias:
Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2). Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante (S) elmenor de los elementos referenciados y se avanza esa referencia una posición.
Pseudocódigo
Como ven, la idea es bastante simple, pero programarla no tanto. Para no dar de golpe la solución, veamosprimero un pseudocódigo del algoritmo:
function mergesort(array A[x..y])
begin
if (x-y > 1)):
array A1 := mergesort(A[x..(int( x+y / 2))])
array A2 := mergesort(A[int(1+(x+y / 2))..y])
returnmerge(A1, A2)
else:
return A
end

function merge(array A1[0..n1], array A2[0..n2])
begin
integer p1 := 0
integer p2 := 0
array R[0..(n1 + n2 + 2)]//suponiendo que n1 y n2 son lasposiciones
//del array y no el length de este mismo, de otro modo seria (n1 + n2)
while (p1 <= n1 or p2 <= n2):
if (p1 <= n1 and A1[p1] <= A2[p2]):
R[p1 + p2] := A1[p1]
p1 := p1 + 1else
if (p2 <= n2 and A1[p1] > A2[p2]):
R[p1 + p2] := A2[p2]
p2 := p2 + 1
return R
end
El código
Básicamente, el pseudocódigo sigue la estrategia descrita anteriormente. Veamos...