Heap Sort in C#

Heap sort:

It is a Comparison-based sorting algorithm, and is part of the Selection Sort family. Although somewhat slower in practice on most machines than a good implementation of Quick Sort, it has the advantage of a more favorable worst-case (n log n) runtime. Heap Sort is an in-place algorithm, but is not a stable sort. Heap Sort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

Heap Sort inserts the input list elements into a heap data structure. The largest value (in a max-heap) is extracted until none remain, the values having been extracted in sorted order. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

namespace DataStructureAlgoriths

{

    class Sort

    {

public void HeapSort()

        {

            long[] inputArray = new long[] { 4, 9, 8, 6, 3, 2, 1 };

            for (int index = (inputArray.Length / 2) - 1; index >= 0; index--)

                Heapify(inputArray, index, inputArray.Length);

            for (int index = inputArray.Length - 1; index >= 1; index--)

            {

                SwapWithTemp(ref inputArray[0], ref inputArray[index]);

                Heapify(inputArray, 0, index - 1);

            }

            foreach (var item in inputArray)

            {

                Console.WriteLine(item);

            }

        }

        private void Heapify(long[] inputArray, int root, int bottom)

        {

            bool completed = false;

            int maxChild;

            while ((root * 2 <= bottom) && (!completed))

            {

                if (root * 2 == bottom)

                    maxChild = root * 2;

                else if (inputArray[root * 2] > inputArray[root * 2 + 1])

                    maxChild = root * 2;

                else

                    maxChild = root * 2 + 1;

                if (inputArray[root] < inputArray[maxChild])

                {

                    SwapWithTemp(ref inputArray[root], ref inputArray[maxChild]);

                    root = maxChild;

                }

                else

                {

                    completed = true;

                }

            }

        }

private void SwapWithTemp(ref long valOne, ref long valTwo)

        {

            long temp = valOne;

            valOne = valTwo;

            valTwo = temp;

        }

}

}

using System;

using System.Collections.Generic;

using System.Text;

namespace DataStructureAlgoriths

{

    class Program

    {

        static void Main(string[] args)

        {

            Sort s = new Sort();

            s.HeapSort();

            Console.ReadLine();

        }

    }

}