Contabilidad De Costos

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 en dividir 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/2 elementos 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 ahoracomo sería la estrategia para mezclar 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) el menor 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 darde golpe la solución, veamos primero 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])
return merge(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 las posiciones
//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 + 1

else
if (p2 <= n2 and A1[p1] > A2[p2]):
R[p1 + p2] := A2[p2]
p2 := p2 + 1return R
end

El código
Básicamente, el pseudocódigo sigue la estrategia descrita anteriormente. Veamos el código en C# de una vez:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSort
{
class Program
{
static void Main(string[] args)
{
//Array desordenado inicial
int[] nums = new int[] { 2,7, 4, 7, 2, 9, 13, 4, 6, 8 };
MergeSort(nums);

//Imprimo el array ya ordenado
for (int i = 0; i < nums.Length; i++)
Console.Write(nums[i]+" ");
Console.ReadLine();
}

//Método portal que llama al método recursivo inicial
public static void MergeSort(int[] x)
{
MergeSort(x, 0, x.Length - 1);
}

static privatevoid MergeSort(int[] x, int desde, int hasta)
{
//Condicion de parada
if (desde == hasta)
return;

//Calculo la mitad del array
int mitad = (desde + hasta) / 2;

//Voy a ordenar recursivamente la primera mitad
//y luego la segunda
MergeSort(x, desde, mitad);
MergeSort(x, mitad + 1, hasta);

//Mezclo las dosmitades ordenadas
int[] aux = Merge(x, desde, mitad, mitad + 1, hasta);
Array.Copy(aux, 0, x, desde, aux.Length);
}

//Método que mezcla las dos mitades ordenadas
static private int[] Merge(int[] x, int desde1, int hasta1, int desde2, int hasta2)
{
int a = desde1;
int b = desde2;
int[] result = new int[hasta1 - desde1 + hasta2 - desde2 +...