Heap Sort

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(nlog n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

(Source: http://en.wikipedia.org/wiki/Heapsort)

    class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        private int[] HeapSort(int[] input)
        {
            temp = input;

            // make the irregular array into heap format
            for (int i = input.Length / 2; i >= 1; i--)
            {
                sweep(i, input.Length);
            }

            // sort the heap
            for (int N = input.Length; N >= 1; )
            {
                Swap(temp, 0, N - 1);
                N--;
                sweep(1, N);

            }
     
            return input;
        }

        private int[] temp;

        private int getElementOneBasedIndex(int oneBasedIndex)
        {
            return temp[oneBasedIndex - 1];
        }

        private int sweep(int i, int N)
        {
            for ( ; i <= N/2;)
            {
                int leftChild = getElementOneBasedIndex(2 * i);
                int rightChild = int.MinValue;
                if (2 * i + 1 <= N)
                {
                    rightChild = getElementOneBasedIndex(2 * i + 1);
                }
                int maxChild = leftChild > rightChild ? 2 * i : 2 * i + 1;
                if (getElementOneBasedIndex(maxChild) > getElementOneBasedIndex(i))
                {
                    Swap(temp, maxChild-1, i-1);
                }
                i = maxChild;
            }
            return i;
           
        }

       

   
        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] Heap = new int[arraySize];
           

            for (int x = 0; x < IteMerge.Length; x++)
            {
                Heap[x] = x;
            }

            for (int x = 0; x < IteMerge.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = Heap[random];
                Heap[random] = IteMerge[x];
                Heap[x] = temp;
            }


            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.HeapSort(Heap);
            StopWtch.Stop();
            Console.WriteLine("HEAPSORT:    " + StopWtch.Elapsed.TotalSeconds + "sec");

            Console.ReadLine();
        }
    }