using FastSort_3102;

/*
 * Fast Sort for CSC 3102 Portfolio
 * Merge Sort O(nlogn)
*/

namespace FastSort_3102
{
    class MergeSort
    {
        public static void Sort(int[] list)
        {
            if(list.Length == 1)
            {
                return;
            }

            int[] left = new int[list.Length / 2];
            int[] right = new int[list.Length - left.Length];

            int j = 0;
            for(int i = 0; i < list.Length; i++)
            {
                if (i < left.Length)
                {
                    left[i] = list[i];
                }
                else
                {
                    right[j] = list[i];
                    j++;
                }
            }

            Sort(left);
            Sort(right);

            int k = 0, l = 0, r = 0; // l -> left index, r -> right index, k-> list index

            while (l < left.Length && r < right.Length)
            {
                if (left[l] < right[r])
                {
                    list[k] = left[l];
                    k++; l++;
                }
                else
                {
                    list[k] = right[r];
                    k++; r++;
                }
            }

            while (l < left.Length)
            {
                list[k] = left[l];
                k++; l++;
            }

            while (r < right.Length)
            {
                list[k] = right[r];
                k++; r++;
            }
        }
    }
}

/*
class Program
{
    static void Main()
    {
        int[] array = new int[100];
        for (int i = 0; i <  array.Length; i++)
        {
            array[i] = new Random().Next(0, 1000);
        }

        MergeSort.Sort(array);

        Console.Write("{ ");
        foreach (int i in array)
        {
            Console.Write(i + ", ");
        }
        Console.WriteLine("}");
        
    }
}
*/