using System;
using System.Text;

namespace Algorithm {
    class Program {
        static void Main(string[] args) {
            // Random 10,000,000 items
            int[] list = new int[10000000];
            Random rnd = new Random();

            for (int i = 0; i < 10000000; i++) {
                list[i] = rnd.Next(0, int.MaxValue);
            }

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();

            int[] tmp = (int[])list.Clone();
            sw.Start();
            MergeSortAlgorithm.MergeInsertionSort(tmp);
            sw.Stop();
            Console.WriteLine("Merge-Insertion Sort: " + sw.ElapsedMilliseconds + " millioseonds");

            tmp = (int[])list.Clone();
            sw.Reset();
            sw.Start();
            MergeSortAlgorithm.MergeSort(tmp);
            sw.Stop();
            Console.WriteLine("Merge Sort: " + sw.ElapsedMilliseconds + " millioseonds");
        }
    }

    class MergeSortAlgorithm {
        public static void MergeSort(int[] array) {
            int[] aux = new int[array.Length];
            MergeSort(array, aux, 0, array.Length - 1);
        }

        public static void MergeSort(int[] array, int[] aux, int low, int high) {
            if (low >= high) return;

            int mid = (low + high) / 2;

            MergeSort(array, aux, low, mid);
            MergeSort(array, aux, mid + 1, high);

            Merge(array, aux, low, mid, high);
        }

        protected static void Merge(int[] array, int[] aux, int low, int mid, int high) {
            // copy into aux array
            for (int i = low; i <= high; i++) aux[i] = array[i];

            // merge
            int j = low, k = mid + 1;
            for (int o = low; o <= high; o++) {
                if (j > mid)
                    array[o] = aux[k++];
                else if (k > high)
                    array[o] = aux[j++];
                else if (aux[k] < aux[j])
                    array[o] = aux[k++];
                else
                    array[o] = aux[j++];
            }
        }

        public static void MergeInsertionSort(int[] array) {
            MergeInsertionSort(array, 0, array.Length - 1);
        }

        public static void MergeInsertionSort(int[] array, int low, int high) {
            if (low >= high) return;
            if (low + 1 == high) {
                // sort two elements
                if (array[low] > array[high]) {
                    int tmp = array[low];
                    array[low] = array[high];
                    array[high] = tmp;
                }
            } else {
                int mid = (low + high) / 2;

                MergeInsertionSort(array, low, mid);
                MergeInsertionSort(array, mid + 1, high);

                // do insertion sort
                for (int i = mid + 1, j; i <= high; i++) {
                    int ins = array[low];

                    // move the element into correct position
                    for (j = i - 1; (j >= low) && (ins < array[j]); j--) {
                        array[j + 1] = array[j];
                    }

                    array[j + 1] = ins;
                }
            }
        }
    }
}