public static void Main (string[] args)
{

        int i;
        int[] arrOne = {503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703};
        int[] arrTwo = {908,897,765,703,677,653,612,512,509,503,426,275,170,154,087,061};
        int[] arrThree = {300};
        int[] arrFour = {0,1,0,0,1,1,1,0,1,0};
        int n = 0;
        string c = String.Empty;

        // the application runs until the user agrees to quit at the end of a sorting run
        do
        {
                // displays the 4 arrrays
                Console.WriteLine ("Assignment: Given are 4 different arrays; You have the choice which one you want to sort.");
                Console.WriteLine ("\n1. Knuths entry sequence:\n   503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703");
                Console.WriteLine ("\n2. Knuths entry sequence descended:\n   908,897,765,703,677,653,612,512,509,503,426,275,170,154,087,061");
                Console.WriteLine ("\n3. Just one number:\n   300");
                Console.WriteLine ("\n4. A set of 0 and 1:\n   0,1,0,0,1,1,1,0,1,0");
                Console.WriteLine ("\n Which array do you want to sort?");
                n = Convert.ToInt32(Console.ReadLine());
                //Console.Clear();
                var comp = new CountingComparer<int>();

                switch (n)
                {
                case 1:
                        for (i = arrOne.Length; i > 1; i--)
                        {
                                HeapSort(arrOne, i - 1, comp);
                        }
                        DisplayArray(arrOne);
                        break;
                case 2:
                        for (i = arrTwo.Length; i > 1; i--)
                        {
                                HeapSort(arrTwo, i - 1, comp);
                        }
                        DisplayArray(arrTwo);
                        break;
                case 3:
                        for (i = arrThree.Length; i > 1; i--)
                        {
                                HeapSort(arrThree, i - 1, comp);
                        }
                        DisplayArray(arrThree);
                        break;
                case 4:
                        for (i = arrFour.Length; i > 1; i--)
                        {
                                HeapSort(arrFour, i - 1, comp);
                        }
                        DisplayArray(arrFour);
                        break;
                default:
                        Console.WriteLine ("\n Array not exist!");
                        break;
                }

                Console.WriteLine("\nThe case needed " + comp.Count + " comparisons!");
                Console.WriteLine("\nDo you want to quit the application? (y/n) ");
                c = Console.ReadLine();
                //Console.Clear();

        }
        while (c != "y");


}

// displays the array
public static void DisplayArray(int[] arr)
{
        Console.WriteLine("\nSorted Array!\n");

        for (int i = 0; i < arr.Length; i++)
                Console.WriteLine ("   " + arr[i]);
}

// sorts the array with the heapsort algorithm
// first the root node gets selected and then the right and left child gets selected
// if value of child is greater than its parent node then they get swapped
// after creating heap condition the algo removes the largest element and places it in the new array of sorted elements
public static void HeapSort<T>(T[] array, int arr_ubound, IComparer<T> comp)
{
        int i, j;
        int lChild, rChild, pNode, root;
        T temp;

        root = (arr_ubound - 1) / 2;

        // for debugging
        //Console.WriteLine ("root " + root);
        //Console.WriteLine ("arr_ubound " + arr_ubound);

        for (j = root; j >= 0; j--)
        {
                for (i = root; i >= 0; i--)
                {
                        lChild = (2*i)+1;
                        rChild = (2*i)+2;

                        if ((lChild <= arr_ubound) && (rChild <= arr_ubound))
                        {
                                if (comp.Compare(array[rChild], array[lChild]) >= 0)
                                        pNode = rChild;
                                else
                                        pNode = lChild;
                        }
                        else
                        {
                                if (rChild > arr_ubound)
                                        pNode = lChild;
                                else
                                        pNode = rChild;
                        }

                        if (comp.Compare(array[i], array[pNode]) < 0)
                        {
                                temp = array[i];
                                array[i] = array[pNode];
                                array[pNode] = temp;
                        }
                }
        }

        temp = array[0];
        array[0] = array[arr_ubound];
        array[arr_ubound] = temp;
        return;
}
public class CountingComparer<T> : Comparer<T>
{
    public int Count { get; private set; }
    IComparer<T> defaultComparer = Comparer<T>.Default;
    public override int Compare(T left, T right)
    {
        this.Count++;
        return defaultComparer.Compare(left, right);
    }
}