Updated on

Heap sort turns an array into a max heap and then moves the largest remaining value to the end of the array, one value per round. The C# code is two short methods that sort the array in place in O(N log N) time.

We first follow the algorithm on a six-element array, then implement it, look at its time and space complexity, and compare it with other sorting algorithms such as merge sort and quicksort.

To download the source code for this article, you can visit our GitHub repository.

So without further ado, let’s begin!

What Is Heap Sort?

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure.

A binary heap is a complete binary tree. In a max heap, every node holds a value greater than or equal to the values of its children, so the largest value always sits at the root. We don’t need tree nodes to build one. A plain array works, because the children of the element at index i sit at indexes 2 * i + 1 and 2 * i + 2.

The algorithm runs in two phases. First, it rearranges the array into a max heap. Then it swaps the root with the last element of the heap, shrinks the heap by one, and heapifies the new root so the max heap property holds again.

Each round puts the largest remaining value in its final place at the end of the array. When only one element is left in the heap, the array is sorted in ascending order.

Let’s take a deep dive and learn how heap sort works. 

How Does the Heap Sort Algorithm Work?

The heap sort algorithm is a sorting technique that belongs to the family of comparison-based sorting algorithms. It uses a data structure called a heap, which is essentially a binary tree with some special properties. The heap sort algorithm has two phases:

1) The heapify phase: In this phase, we transform the input array into a max heap: a binary tree in which the value of each node is greater than or equal to the value of its children nodes. This can be done by starting at the last non-leaf node in the tree and working backward towards the root, ensuring that each node satisfies the max heap property.

2) The sort phase: In this phase, we repeatedly remove the root of the max heap until only one element remains. This is done by swapping the root node with the last element in the heap, and then ensuring that the new root node satisfies the max heap property. This process is repeated until only one element remains in the heap.

Let’s look at an example of how heap sort works. We will use the following set of numbers:

int[] array = {12, 2, 24, 51, 8, -5};

The first step is to transform the array into a max heap whereby, the largest element of the array resides at the root. Here, we see the visual representation of the array as a binary tree and its max heap representation:

The array 12, 2, 24, 51, 8, -5 drawn as a binary tree, and the same array after building the max heap: 51, 12, 24, 2, 8, -5.

Once we build the initial max heap, we swap the last element of the heap with the current root and remove the last element, which now holds the largest value, from the heap.

We apply the heapify function to convert the heap into a max heap and repeat the last step until the number of elements in the heap is one. When we reach this point, the array’s elements are in ascending order. 

Let’s visualize the steps we are going to take to sort our current example:

Ten steps of heap sort on the max heap 51, 12, 24, 2, 8, -5: each step after the first either swaps the root with the last heap element or restores the max heap, until -5, 2, 8, 12, 24, 51 remain in order.

The two-headed arrows in the odd-numbered steps mark the swap that comes next, and the blue circles are the values already in their final place.

After step 10, the sorting process is complete and the array becomes:

-5, 2, 8, 12, 24, 51

Let’s learn how to implement the heap sort algorithm in C#.

How to Implement Heap Sort in C#?

In a HeapSortMethods class of a new console app, let’s write a function SortArray() that takes an array and its size as inputs and returns the same array, sorted:

public int[] SortArray(int[] array, int size)
{
    if (size <= 1)
        return array;

    for (int i = size / 2 - 1; i >= 0; i--)
    {
        Heapify(array, size, i);
    }

    for (int i = size - 1; i >= 0; i--)
    {
        var tempVar = array[0];
        array[0] = array[i];
        array[i] = tempVar;

        Heapify(array, i, 0);
    }

    return array;
}

Let’s understand how the code works.

After checking whether the array has one element or is empty, the first loop calls the Heapify() function which builds the max heap:

for (int i = size / 2 - 1; i >= 0; i--)
{
    Heapify(array, size, i);
}

In the second loop, we swap the last element of the max heap with the first element, rebuild the max heap, and return the sorted array:

for (int i = size - 1; i >= 0; i--)
{
    var tempVar = array[0];
    array[0] = array[i];
    array[i] = tempVar;

    Heapify(array, i, 0);
}

return array;

Next, let’s implement the Heapify() function in the same class, which takes an array, the size of the heap, and the index of the node it should fix as arguments:

static void Heapify(int[] array, int size, int index)
{
    var largestIndex = index;
    var leftChild = 2 * index + 1;
    var rightChild = 2 * index + 2;

    if (leftChild < size && array[leftChild] > array[largestIndex])
    {
        largestIndex = leftChild;
    }

    if (rightChild < size && array[rightChild] > array[largestIndex])
    {
        largestIndex = rightChild;
    }

    if (largestIndex != index)
    {
        var tempVar = array[index];
        array[index] = array[largestIndex];
        array[largestIndex] = tempVar;

        Heapify(array, size, largestIndex);
    }
}

Max Heap Implementation 

Let’s understand how the Heapify() function works. First, we set the index of the maximum element to the current array index and set the indexes of the left and right children:

var largestIndex = index;
var leftChild = 2 * index + 1;
var rightChild = 2 * index + 2;

Next, we check if the left child is greater than the current root element and, if it is, store its index in largestIndex:

if (leftChild < size && array[leftChild] > array[largestIndex])
{
    largestIndex = leftChild;
}

We repeat the same process and check if the right child is greater than the largest value so far, and store its index if it is:

if (rightChild < size && array[rightChild] > array[largestIndex])
{
    largestIndex = rightChild;
}

On the other hand, if the index of the maximum element is not equal to the current index, we swap the positions of array[largestIndex] and array[index] and recursively call the Heapify() function on the affected subtree until we build the max heap: 

if (largestIndex != index)
{
    var tempVar = array[index];
    array[index] = array[largestIndex];
    array[largestIndex] = tempVar;

    Heapify(array, size, largestIndex);
}

Each recursive call moves one level down the tree, so Heapify() never goes deeper than the height of the heap. For the 2,000,000-element arrays in our benchmark, that is at most 21 nested calls.

Finally, in a test method of an MSTest project that references our app, we can verify that the SortArray() method sorts a given unsorted array accurately:

var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new HeapSortMethods();

var sortedArray = sortFunction.SortArray(array, array.Length);

Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(expected, sortedArray);

What Is the Time and Space Complexity of Heap Sort?

Heap sort runs in O(N log N) time in the best, average and worst case when the values are distinct. It needs O(1) extra space for the sort itself, it sorts in place, and it is not stable.

The time splits between the two phases. Building the max heap takes O(N). After that, each of the N removals calls Heapify() once, and Heapify() walks down one path of the tree, which is about log2 N levels long.

The one faster case is an array of identical values. Heapify() never finds a larger child, so every call stops after at most two comparisons, and the sort takes O(N) time. For 2,000,000 equal values, we counted 5,999,994 comparisons, against 77,585,015 for 2,000,000 random ones.

For space, the algorithm needs no second array, only the tempVar variable during a swap. Our recursive Heapify() adds one call per tree level, up to about log2 N calls on the stack.

Best-Case Time Complexity

The heap sort algorithm encounters its best-case time complexity when all the elements are identical. Every Heapify() call compares the node with its children, finds no larger value and returns without a swap, so each of the N removals takes constant time O(1), and the whole sort takes N * O(1) time, or O(N).

That case is rare in practice. As soon as the values are distinct, the best case is O(N log N): even for an array that is already sorted, Heapify() walks most of the way down the tree after each removal.

Average-Case Time Complexity

The heap sort algorithm has an average-case time complexity of O(N log N) just like its best-case time complexity. This scenario occurs when we use random array elements. Each Heapify() call costs up to O(log N), one step per level of the heap, and we call it about N times, which gives O(N log N).

Worst-Case Time Complexity

Heap sort has a worst-case time complexity of O(N log N) just like its average-case time complexity. The algorithm is highly likely to encounter this case when all the elements are distinct.

This means we need to call the Heapify() function every time we remove an element from the heap.

Among our test inputs, the sorted array makes the most comparisons: 79,472,176 for 2,000,000 elements, against 77,585,015 for random values. The difference is under 3 percent, and both stay O(N log N).

Advantages of Heap Sort Algorithm

Heap sort is an in-place sorting algorithm. This means it does not require additional storage for the heap data structure when we implement it using arrays.

Besides that, the algorithm does not need a second array to run, unlike sorting algorithms such as merge sort, which needs O(N) extra space.

On large random arrays, heap sort performs better than other sorting algorithms such as insertion sort and bubble sort, which need O(N²) time. On an array that is almost sorted, insertion sort can still win, because its best case is O(N).

Heap sort is a close relative of selection sort. Selection sort picks the smallest remaining value in every round and moves it to the front, and heap sort picks the largest and moves it to the end. Selection sort scans the whole unsorted part for its value, which costs O(N) per round, while the heap keeps the largest value at the root and needs only O(log N) to restore itself after each removal.

Its worst case also stays O(N log N), which quicksort cannot promise. That is why .NET keeps heap sort as a safety net. Microsoft Learn describes the switch in the remarks for Array.Sort(): “If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.” Our quicksort article explains the rest of what Array.Sort() does.

If we need a heap itself rather than a sort, for example to always take the smallest item next, .NET has one built in: PriorityQueue<TElement, TPriority>, which we cover in our priority queue article.

Disadvantages of Heap Sort Algorithm

Heap sort is not a stable sorting algorithm. This means that if there are two elements with the same key value, their order in the sorted array is not necessarily maintained just like quicksort.

We can see it with the same algorithm, sorting the pairs (3, a), (1, b), (3, c), (2, d), (1, e) by their numbers only. The result is (1, b) (1, e) (2, d) (3, c) (3, a): the two 3s come out in reverse order. The swap that moves the root to the end of the array jumps over values that are equal to it.

It is not as simple to implement as other algorithms such as bubble sort.

Performance Tests

Let’s test how long the algorithm takes for it to sort three arrays that have 2,000,000 elements each. To help us complete these tests, we are going to implement three methods in our HeapSortMethods class. 

First, let’s write a method to generate a set of random array elements:

public static int[] CreateRandomArray(int size, int lower, int upper)
{
    var array = new int[size];
    var rand = new Random();

    for (int i = 0; i < size; i++)
        array[i] = rand.Next(lower, upper);

    return array;
}

The CreateRandomArray() method takes three integers size, lower and upper. Using the inbuilt Random class, we generate integer values between lower and upper that we’re going to put into the array, which we are going to use to test the average-case time complexity.

Next, we are going to simulate the worst-case time complexity scenario by defining a method CreateSortedArray() that returns a sorted array (every element is going to be distinct): 

public static int[] CreateSortedArray(int size)
{
    var array = new int[size];

    for (int i = 0; i < size; i++)
        array[i] = i;

    return array;
}

To simulate the best-case time complexity scenario, we are going to define a method  CreateIdenticalArray() that populates the array with the same elements:

public static int[] CreateIdenticalArray(int size, int lower, int upper)
{
    var array = new int[size];
    var rand = new Random();

    var selectedElement = rand.Next(lower, upper);

    for (int i = 0; i < size; i++)
    {
        array[i] = selectedElement;
    }

    return array;
}

Here, we see that we select a random number and populate the array with that selected number.  

The Benchmark Class

BenchmarkDotNet measures a method by calling it again and again, and our SortArray() leaves the array it receives sorted. If all those calls shared one array, the random input would be random exactly once, for the first call.

The class below therefore keeps the generated numbers in _source and copies them into _work at the start of each call:

public class HeapSortBenchmarks
{
    private const int Size = 2_000_000;

    private readonly HeapSortMethods _heapSort = new();
    private int[] _source = [];
    private int[] _work = [];

    [Params("Random", "Sorted", "Identical")]
    public string Input { get; set; } = "Random";

    [GlobalSetup]
    public void Setup()
    {
        _source = Input switch
        {
            "Sorted" => HeapSortMethods.CreateSortedArray(Size),
            "Identical" => HeapSortMethods.CreateIdenticalArray(Size, 1, Size),
            _ => HeapSortMethods.CreateRandomArray(Size, 1, Size)
        };
        _work = new int[Size];
    }

    [Benchmark]
    public int[] SortArray()
    {
        _source.CopyTo(_work, 0);

        return _heapSort.SortArray(_work, Size);
    }
}

Setup() runs before the timed calls of each Input value and fills the source array with random, sorted or identical numbers. The copy of 2,000,000 integers takes less than a millisecond, which is small next to a sort of the same array.

Sample Test Results

The class goes in its own file in our console app. We add the BenchmarkDotNet package to the app, start the class file with using BenchmarkDotNet.Attributes;, and call BenchmarkRunner.Run<HeapSortBenchmarks>(); from its Program.cs, after using BenchmarkDotNet.Running;. Let’s run it in Release mode and assess the sample best, average, and worst-case complexity performance results of the algorithm:

| Method    | Input     | Mean       | Error     | StdDev    |
|---------- |---------- |-----------:|----------:|----------:|
| SortArray | Identical |   3.721 ms | 0.0425 ms | 0.0377 ms |
| SortArray | Random    | 244.424 ms | 4.8101 ms | 7.3455 ms |
| SortArray | Sorted    | 125.979 ms | 2.4119 ms | 2.2561 ms |

The array of identical values sorts in about 4 milliseconds, more than 30 times faster than the others. Here we see the O(N) best case: Heapify() returns after its comparisons and never recurses. The copy, under a millisecond, is a visible part of that time and hardly registers in the other two rows.

The random array is the slowest, at about 240 milliseconds, while the sorted array takes about 130. Our counts show the sorted array needs slightly more comparisons and swaps than the random one, so the extra time on random data does not come from extra work. The processor runs the same comparisons faster when the data follows a pattern.

An earlier version of this benchmark sorted the same array on every call, so its “Average Case” row measured sorted data after the first call. That is why the random and sorted rows looked almost the same there.

One array size cannot show how the time grows, but our counts can. Going from 2,000 to 2,000,000 random values, 1,000 times more elements, the number of comparisons grew about 2,060 times, close to the 1,900 times that N log N predicts. Please note that these runtimes may change depending on the number of elements and the computing resources available. 

Conclusion

In this article, we have learned how heap sort in C# works and its time and space complexity. In case you’d like to learn how to implement another sorting algorithm, check out some of our other sorting algorithm articles.

Heap sort never takes more than O(N log N) time and needs no second array. In return, it loses the order of equal values, and in our benchmark it ran slower on random data than on sorted data. Our own code rarely needs to call it directly, because Array.Sort() already falls back to heap sort when its quicksort runs into trouble.

Tested with .NET 10.0.10, BenchmarkDotNet 0.15.8 and MSTest 4.5.2.