using System;

namespace Practica1Tema4
{
    class Practica1Tema4
    {
        public static void mergeSort(int[] arr, int izq, int der)
        {
            if (izq < der)
            {
                int mitad = (izq + der) / 2;

                mergeSort(arr, izq, mitad);
                mergeSort(arr, mitad + 1, der);
                merge(arr, izq, mitad, der);
            }
        }

        public static void merge(int[] arr, int izq, int mitad, int der)
        {
            int n1 = mitad - izq + 1;
            int n2 = der - mitad;

            int[] L = new int[n1];
            int[] R = new int[n2];

            for (int i = 0; i < n1; i++) L[i] = arr[izq + i]; //Mitad Izquierda
            for (int j = 0; j < n2; j++) R[j] = arr[mitad + 1 + j]; //Mitad Derecha

            //Vamos a fusionar

            int i1 = 0, j1 = 0, k = izq;

            while (i1 < n1 && j1 < n2)
            {
                if (L[i1] <= R[j1])
                {
                    arr[k++] = L[i1++]; //Forma temporal
                }
                else
                {
                    arr[k++] = R[j1++];
                }
            }

            while (i1 < n1) arr[k++] = L[i1++];
            while (j1 < n2) arr[k++] = R[j1++];
        }

        static void Main(string[] args)
        {
            int[] arr = { 38, 27, 43, 3, 9, 82, 10 };

            Console.WriteLine("Arreglo original:");
            foreach (int num in arr)
            {
                Console.Write(num + " ");
            }

            mergeSort(arr, 0, arr.Length - 1);

            Console.WriteLine("\n\nArreglo ordenado:");
            foreach (int num in arr)
            {
                Console.Write(num + " ");
            }

            String[] nombres =
            {
                "Carlos",
                "Meli",
                "Ivan",
                "Tonio",
                "Monse",
                "Edgar",
                "Ximena"
            };

            Console.WriteLine("\n\nNombres originales:");

            foreach (String nombre in nombres)
            {
                Console.Write(nombre + " ");
            }

            ArregloNombres.mergeSort(nombres, 0, nombres.Length - 1);

            Console.WriteLine("\n\nNombres ordenados:");

            foreach (String nombre in nombres)
            {
                Console.Write(nombre + " ");
            }
        }
    }
}