Algoritmos de ordenación en c# - Algoritmo Merge Sort

2. Algoritmo Merge Sort

•  En este capítulo del curso de programación en c# con visual studio 2017 vamos a continuar viendo algunos algoritmos de ordenación de vectores o arrays. En esta ocasión veremos el algoritmo de ordenación por mezcla o Merge Sort.

• Este algoritmo  se basa en la técnica divide y vencerás.Esta técnica consiste en dividir el problema a resolver en  problemas más pequeños del mismo tipo que a su vez se  volverán a dividir en problemas todavía mas pequeños hasta que sean  triviales.

• Os dejo un enlace al pseudocódigo y a  información más detallada sobre este algoritmo: https://es.wikipedia.org/wiki/Ordenamiento_por_mezcla

• Una vez visto esto ya podemos ver el vídeo con la explicación:

• También os dejo el código correspondiente al algoritmo explicado en el vídeo:

 public static void Mergesort()
        {
            int[] array = { 12, 17, 16, 8, 67, 1, 4, 1000, 99, 77, 6, 10 ,88, 45 };
            mostrar(array);
            Console.WriteLine("");
            MergeSort(array, 0, array.Length - 1);
            Console.ReadLine();
            mostrar(array);
            Console.ReadLine();

        }


        static private void MergeSort(int[] array, int inicio, int fin)
        {

            if (inicio == fin)
                return;

             int mitad = (inicio + fin) / 2;

            MergeSort(array, inicio, mitad);
            MergeSort(array, mitad + 1, fin);

             int[] aux = juntarArrays(array, inicio, mitad, mitad + 1, fin);

            Array.Copy(aux, 0, array, inicio, aux.Length);

            Console.WriteLine("");

            mostrar(array);

        }

    static private int[] juntarArrays(int[] x, int inicio, int fin, int inicio2, int fin2)
        {

            int aux1 = inicio;
            int aux2 = inicio2;
            int[] resultado = new int[fin - inicio + fin2 - inicio2 + 2];

            for (int i = 0; i < resultado.Length; i++)
            {

                if (aux2 != x.Length)
                {

                    if (aux1 > fin && aux2 <= fin2)
                    {
                        resultado[i] = x[aux2];
                        aux2++;
                    }

                    if (aux2 > fin2 && aux1 <= fin)
                    {
                        resultado[i] = x[aux1];
                        aux1++;
                    }

                    if (aux1 <= fin && aux2 <= fin2)
                    {
                        if (x[aux2] <= x[aux1])
                        {
                            resultado[i] = x[aux2];
                            aux2++;
                        }
                        else
                        {
                            resultado[i] = x[aux1];
                            aux1++;

                        }

                    }

                }
                else
                {
                    if (aux1 <= fin)
                    {
                       resultado[i] = x[aux1];
                        aux1++;
                    }

                }

            }
            return resultado;

        }