Heap Sort in C, C++, Java, Python and C#: Heaps, Sift-Down and Real Costs

Heap sort has the guarantee quicksort lacks and the memory use merge sort lacks: O(n log n) on every input, sorted in place. On 10,000 values its comparison count stayed between 217,379 and 244,460 across four very different inputs. It pays for that in speed. On random integers it took up to 1.5 times as long as a quicksort up to a million elements, and 1.7–2.1 times as long at ten million, under two compilers.

This guide shows how a heap is stored in an array and traces heap sort on a small example. It gives implementations in C, C++, Java, Python and C#, and measures the two ways to build a heap, Floyd’s variant that saves 41% of the comparisons, and the timing gap with quicksort. It closes with three index mistakes, one of which sorted the article’s own example correctly and failed on 8.7% of random inputs. Every program was compiled and run for this article on Ubuntu 24.04: C with GCC 13.3 and Clang 18.1.3 (-std=c11 and -std=c17), C++ with g++ 13.3 and clang++ 18.1.3 (-std=c++17 and -std=c++20), all with -Wall -Wextra -pedantic and no warnings except where a pitfall is shown; Java on OpenJDK 21, Python 3.11 (also checked with ruff and mypy --strict), and C# on .NET 10 with analyzer warnings as errors. All five sort the same array and print the same result. The C and C++ code is in GitHub repositories whose builds run the tests on each change.

What Is Heap Sort?

Heap sort is a comparison sorting algorithm that arranges the array into a binary max-heap, in which every element is at least as large as its children, and then repeatedly swaps the largest element (at the root) to the end of the array and restores the heap in the part that remains. It sorts in place with O(1) extra memory, runs in O(n log n) time in the worst case, and is not stable.

It is selection sort with a better data structure. Both repeatedly take the largest (or smallest) remaining element; selection sort finds it with an O(n) scan, heap sort keeps the remaining elements in a heap so that each removal costs O(log n). The algorithm was published by J. W. J. Williams in 1964, and the O(n) bottom-up way of building the heap by Robert W. Floyd the same year; NIST’s Dictionary of Algorithms and Data Structures lists both papers. Heap sort’s worst-case guarantee is why it appears inside other sorts: libstdc++’s std::sort and OpenJDK’s Arrays.sort for primitive arrays both switch to heap sort when quicksort’s recursion goes too deep.

How a Heap Lives in an Array

A binary heap needs no pointers. For an array indexed from 0, the children of index i are at 2i + 1 and 2i + 2, and its parent is at (i − 1) / 2. The heap property says every element is at least as large as its children, which puts the largest value at index 0.

Two operations maintain the property:

• Sift down: an element that may be too small for its position is swapped with its larger child until neither child is larger. This is how the root is restored after the largest element is removed.
• Sift up: an element that may be too large is swapped with its parent until the parent is not smaller. This is how an element is inserted.

How Heap Sort Works

1. Build a max-heap from the whole array. The efficient way is to sift down every internal node, starting from the last parent at index n/2 − 1 and working back to the root.
2. Swap a[0], the largest element, with the last element of the heap. The largest is now in its final position.
3. Shrink the heap by one and sift down the new root.
4. Repeat steps 2 and 3 until the heap has one element.

Worked Example

Sorting 29 10 14 37 13 5 41 22, as printed by the trace program in the repository. The | separates the heap on the left from the sorted tail on the right:

Output:

start:                   29   10   14   37   13    5   41   22
max-heap built:          41   37   29   22   13    5   14   10
extract 41:              37   22   29   10   13    5   14 | 41
extract 37:              29   22   14   10   13    5 | 37   41
extract 29:              22   13   14   10    5 | 29   37   41
extract 22:              14   13    5   10 | 22   29   37   41
extract 14:              13   10    5 | 14   22   29   37   41
extract 13:              10    5 | 13   14   22   29   37   41
extract 10:               5 | 10   13   14   22   29   37   41

Building the heap moved 41 from index 6 to the root and 29 down to index 2, where it sits above 5 and 14. After that, each line takes the root, swaps it behind the |, and sifts the new root down. After “extract 41” the root is 37, the larger of the two children that 41 left behind, because 10, swapped up from the end, sank past it.

Heap Sort in C

The header declares the sort, Floyd’s variant, and both heap-building methods, which are measured separately below:

/* heap_sort.h - heap sort for int arrays, and the two ways to build a heap */
#ifndef HEAP_SORT_H
#define HEAP_SORT_H

#include <stddef.h>

void heap_sort(int a[], size_t n);         /* sift-down, bottom-up build  */
void heap_sort_floyd(int a[], size_t n);   /* Floyd's leaf-first variant  */

void make_heap_down(int a[], size_t n);    /* bottom-up build: O(n)       */
void make_heap_up(int a[], size_t n);      /* insert one at a time: O(n log n) */

#endif

/* heap_sort.c - heap sort in C11, with a max-heap stored in the array:
 * the children of index i are at 2i + 1 and 2i + 2, its parent at (i - 1) / 2.
 * SORT_LESS(x, y) means "x sorts before y". Test programs redefine it
 * before including this file, to count comparisons. */
#include "heap_sort.h"

#ifndef SORT_LESS
#define SORT_LESS(x, y) ((x) < (y))
#endif

static void swap_int(int *x, int *y) { int t = *x; *x = *y; *y = t; }

/* Moves a[root] down until neither child is larger. The heap is a[0..n). */
static void sift_down(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t child = 2 * root + 1;
        if (child >= n)
            return;                          /* root is a leaf */
        if (child + 1 < n && SORT_LESS(a[child], a[child + 1]))
            child++;                         /* the larger child */
        if (!SORT_LESS(a[root], a[child]))
            return;                          /* heap order holds */
        swap_int(&a[root], &a[child]);
        root = child;
    }
}

/* Moves a[i] up until its parent is not smaller. */
static void sift_up(int a[], size_t i)
{
    while (i > 0) {
        size_t parent = (i - 1) / 2;
        if (!SORT_LESS(a[parent], a[i]))
            return;
        swap_int(&a[parent], &a[i]);
        i = parent;
    }
}

/* Floyd's bottom-up heapify: fix the subtrees from the last parent back. */
void make_heap_down(int a[], size_t n)
{
    for (size_t i = n / 2; i-- > 0; )        /* n / 2 - 1 down to 0, no wrap */
        sift_down(a, i, n);
}

/* Builds the heap by inserting a[1], a[2], ... one at a time. */
void make_heap_up(int a[], size_t n)
{
    for (size_t i = 1; i < n; i++)
        sift_up(a, i);
}

/* In place, O(n log n) worst case, not stable. */
void heap_sort(int a[], size_t n)
{
    make_heap_down(a, n);
    for (size_t end = n; end > 1; end--) {
        swap_int(&a[0], &a[end - 1]);        /* largest to its final place */
        sift_down(a, 0, end - 1);
    }
}

/* Floyd's variant: the element moved to the root is almost always small,
 * so walk the larger-child path all the way to a leaf without comparing
 * against it (one comparison per level instead of two), then climb back
 * up to where it belongs. */
void heap_sort_floyd(int a[], size_t n)
{
    make_heap_down(a, n);
    for (size_t end = n; end > 1; end--) {
        size_t m = end - 1;                  /* heap is a[0..m) after the swap */
        int v = a[m];
        a[m] = a[0];                         /* largest to its final place */
        size_t hole = 0;
        for (;;) {                           /* 1. descend to a leaf */
            size_t child = 2 * hole + 1;
            if (child >= m)
                break;
            if (child + 1 < m && SORT_LESS(a[child], a[child + 1]))
                child++;
            a[hole] = a[child];
            hole = child;
        }
        while (hole > 0) {                   /* 2. climb back up to v's place */
            size_t parent = (hole - 1) / 2;
            if (!SORT_LESS(a[parent], v))
                break;
            a[hole] = a[parent];
            hole = parent;
        }
        a[hole] = v;
    }
}

A short program that calls them:

/* heap_example.c - builds a heap, then sorts, with both variants */
#include <stdio.h>
#include <limits.h>
#include "heap_sort.h"

static void print_array(const char *label, const int a[], size_t n)
{
    printf("%-10s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", a[i]);
    printf("\n");
}

int main(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int b[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int h[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int edge[] = { 0, INT_MAX, -1, INT_MIN, 0 };
    size_t n = sizeof a / sizeof a[0];

    print_array("before:", a, n);
    make_heap_down(h, n);
    print_array("max-heap:", h, n);
    heap_sort(a, n);
    print_array("sorted:", a, n);
    heap_sort_floyd(b, n);
    print_array("floyd:", b, n);
    heap_sort(edge, 5);
    print_array("limits:", edge, 5);
    heap_sort(NULL, 0);                      /* empty: no loop runs */
    return 0;
}

Output:

before:    29 10 14 37 13 5 41 22
max-heap:  41 37 29 22 13 5 14 10
sorted:    5 10 13 14 22 29 37 41
floyd:     5 10 13 14 22 29 37 41
limits:    -2147483648 -1 0 0 2147483647

The details that carry the correctness:

• child >= n is checked before any child is read. The second child is read only if child + 1 < n.
• The build loop is for (size_t i = n / 2; i-- > 0; ). It visits n/2 − 1 down to 0 without computing n/2 − 1 for small n and without an unsigned i >= 0 test. Both of those are mistakes shown below.
• Sift-down is a loop, not recursion, so heap sort needs no stack beyond a few variables.
• Equal children: SORT_LESS(a[child], a[child + 1]) picks the right child only when it is strictly larger. Either choice would be correct; this one saves a swap on ties.

Building a Heap: Bottom-Up vs One Insertion at a Time

There are two ways to turn an array into a heap. make_heap_down() sifts down each parent from the last one back to the root; make_heap_up() treats the array as a stream of insertions and sifts each new element up. The counting program measured both:

Output:

building a heap: comparisons (and per element)
input                n       bottom-up (down)         insertion (up)
random           10000         18848 ( 1.88)         22946 ( 2.29)
sorted           10000         19982 ( 2.00)        113631 (11.36)
reversed         10000          9999 ( 1.00)          9999 ( 1.00)
10 distinct      10000         18108 ( 1.81)         19900 ( 1.99)
random         1000000       1881471 ( 1.88)       2282710 ( 2.28)
sorted         1000000       1999974 ( 2.00)      17951445 (17.95)
reversed       1000000        999999 ( 1.00)        999999 ( 1.00)
10 distinct    1000000       1816919 ( 1.82)       1995276 ( 2.00)

sorting n = 10000: comparisons; n log2 n = 132877
input             heap_sort heap_sort_floyd
random               235343         138789
sorted               244460         142497
reversed             226682         131029
10 distinct          217379         138448

The bottom-up build never needed more than 2.00 comparisons per element, at 10,000 or at 1,000,000 elements. That is the O(n) bound: most nodes are near the bottom of the tree, where a sift-down is short. Building by insertion reached 11.36 comparisons per element at 10,000 and 17.95 at 1,000,000 on sorted input, where every new element is the largest so far and climbs all the way to the root. That is the O(n log n) case, growing with log₂ n. On random input the insertion build was far cheaper, 2.28 comparisons per element at both sizes, because a random new element usually stops within a level or two. Its worst case is the whole difference between the two methods.

The build is a small part of heap sort’s total: 18,848 of the 235,343 comparisons on the random 10,000-element input.

Floyd’s Variant: 41% Fewer Comparisons

The second table above compares the standard sort with heap_sort_floyd(). The standard sift-down makes two comparisons per level: one to pick the larger child, one to check whether the element has reached its place. But the element being sifted is the one just taken from the end of the heap, which is almost always small, so it nearly always goes to the bottom. Floyd’s variant skips the second comparison on the way down: it moves the larger child up at every level until it reaches a leaf, then climbs back up to the element’s place, usually a level or two.

On 10,000 random values that cut comparisons from 235,343 to 138,789, a 41% saving that brings heap sort within about 4% of n log₂ n = 132,877. The time saving was smaller, and it depended on the compiler, as the next section shows. For int values a comparison is cheap; the variant pays off more when comparisons are expensive, such as strings or records compared through a function.

How This Was Measured

No CPU pinning or frequency-scaling control was used, no hardware counters were read, and all timings come from this one virtual machine.

Heap Sort vs Quicksort as n Grows

One run of the timing program built with GCC:

Output:

ms, random ints, median of 5
         n   heap sort       floyd   quicksort  heap / quick
     10000        0.85        0.74        0.64         1.33x
    100000       11.27       10.16        8.18         1.38x
   1000000      148.39      131.35       99.44         1.49x
  10000000     2126.23     1961.47     1106.10         1.92x

Across three runs per compiler, the ratio of heap sort’s time to quicksort’s:

Two findings:

• Heap sort fell further behind quicksort as the array grew, under both compilers. At 10,000 elements (40 KB of ints) the ratio was at most 1.33; at 10,000,000 (40 MB) it was at least 1.67. Both algorithms make O(n log n) comparisons, and heap sort’s count is not much higher. The likeliest explanation is memory access: a sift-down from index i next reads 2i + 1, so in a large heap each step down the tree jumps to a part of the array that is not in cache, while quicksort’s partition scans the array in order. That is an inference from the trend; no cache-miss counters were read.
• Floyd’s variant was faster with GCC and not with Clang. GCC’s build ran 8–14% faster at every size. Clang’s build of the standard version was already faster than GCC’s, and its Floyd build was no faster and sometimes slower. The 41% comparison saving did not become a consistent time saving for int values.

Three Heap Index Mistakes

1. The 1-Based Child Formula on a 0-Based Array

Many textbooks store the heap from index 1, where the children of i are 2i and 2i + 1. Used on a C array that starts at 0, the formula makes index 0 its own child and skips index 1’s real children. The result can still look right:

/* one_based.c - the 1-based child formulas 2i and 2i + 1 on a 0-based array */
#include <stdio.h>
#include <stddef.h>

static void sift_down_1based(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t child = 2 * root;             /* right for a[1..n], wrong for a[0..n) */
        if (child >= n)
            return;
        if (child + 1 < n && a[child] < a[child + 1])
            child++;
        if (!(a[root] < a[child]))
            return;
        int t = a[root]; a[root] = a[child]; a[child] = t;
        root = child;
    }
}

static void heap_sort_1based(int a[], size_t n)
{
    for (size_t i = n / 2; i-- > 0; )
        sift_down_1based(a, i, n);
    for (size_t end = n; end > 1; end--) {
        int t = a[0]; a[0] = a[end - 1]; a[end - 1] = t;
        sift_down_1based(a, 0, end - 1);
    }
}

static void show(const char *label, const int a[], size_t n)
{
    printf("%s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", a[i]);
    printf("\n");
}

int main(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };   /* the article's example */
    int b[] = { 45, 9, 84, 35, 95 };               /* found by random search */
    heap_sort_1based(a, 8);
    heap_sort_1based(b, 5);
    show("example:", a, 8);
    show("other:  ", b, 5);
    return 0;
}

Output (GCC and Clang, identical):

example: 5 10 13 14 22 29 37 41
other:   9 35 45 95 84

The article’s example came out sorted. The second input, 45 9 84 35 95, did not: 95 and 84 are in the wrong order. A search program in the repository sorted 100,000 random arrays of 2 to 16 values with the same function:

8651 of 100000 random arrays not sorted

It failed on 8.7% of them. A bug that passes the example used to develop it and fails one time in twelve on random input is the kind a test suite of a few hand-written cases will not find. Test a sort against a reference on thousands of random inputs, as the repository’s tests do.

2. An Unsigned Build Loop

The build loop is often written for (i = n / 2 - 1; i >= 0; i--). With a size_t index, i >= 0 is always true:

/* unsigned_build.c - the textbook build loop with a size_t index */
#include <stdio.h>
#include <stddef.h>

static void sift_down(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t child = 2 * root + 1;
        if (child >= n)
            return;
        if (child + 1 < n && a[child] < a[child + 1])
            child++;
        if (!(a[root] < a[child]))
            return;
        int t = a[root]; a[root] = a[child]; a[child] = t;
        root = child;
    }
}

int main(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    size_t n = sizeof a / sizeof a[0];
    for (size_t i = n / 2 - 1; i >= 0; i--)  /* i >= 0 is always true */
        sift_down(a, i, n);
    printf("heap built: %d\n", a[0]);
    return 0;
}

GCC’s -Wextra flags it; Clang 18’s -Wall -Wextra printed no warning:

unsigned_build.c:24:34: warning: comparison of unsigned expression in '>= 0' is always true [-Wtype-limits]

This version does not crash. After i wraps past zero to SIZE_MAX, 2 * i + 1 also wraps, to a value far above n, so sift_down() returns at once without touching memory. The loop then counts down through about 2⁶⁴ values doing nothing. The GCC and Clang builds at -O2, a GCC build at -O0, and a build with AddressSanitizer and UndefinedBehaviorSanitizer all printed nothing and were still running when stopped after 20 seconds. The sanitizers had nothing to report: no memory was accessed out of bounds, and unsigned wraparound is defined behavior. The program looks hung, not broken. The same expression also fails a second way: for n of 0 or 1, n / 2 - 1 is itself SIZE_MAX.

3. child <= n Instead of child < n

An off-by-one in the bound lets sift_down() treat a[n], one element past the heap, as a child:

/* child_bound.c - "child <= n" instead of "child < n" in sift_down */
#include <stdio.h>
#include <stddef.h>

static void sift_down(int a[], size_t root, size_t n)
{
    for (;;) {
        size_t child = 2 * root + 1;
        if (child > n)                       /* should be child >= n */
            return;
        if (child + 1 <= n && a[child] < a[child + 1])
            child++;
        if (!(a[root] < a[child]))
            return;
        int t = a[root]; a[root] = a[child]; a[child] = t;
        root = child;
    }
}

int main(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    size_t n = sizeof a / sizeof a[0];
    for (size_t i = n / 2; i-- > 0; )
        sift_down(a, i, n);
    for (size_t end = n; end > 1; end--) {
        int t = a[0]; a[0] = a[end - 1]; a[end - 1] = t;
        sift_down(a, 0, end - 1);
    }
    for (size_t i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

During the build, a[n] is past the end of the array itself. The results over repeated runs:

When the value past the end is larger than the root, the swap writes the root outside the array and brings the outside value in. What that value is depends on what the stack holds, which is why the Clang build printed a different number each time. The loop bound must be child < n, and the right-child test child + 1 < n.

Heap Sort Time and Space Complexity

Heap Sort in C++, Java, Python and C#

C++

The template sorts any random-access range with a comparator; the heap is a max-heap with respect to comp, so std::greater<>{} gives descending order. The demo also uses the standard library’s heap tools:

// heap_sort.hpp - generic heap sort for C++17
#ifndef HEAP_SORT_HPP
#define HEAP_SORT_HPP

#include <functional>
#include <iterator>
#include <utility>

namespace detail {

template <class RandomIt, class Diff, class Compare>
void sift_down(RandomIt first, Diff root, Diff n, Compare& comp)
{
    for (;;) {
        Diff child = 2 * root + 1;
        if (child >= n)
            return;
        if (child + 1 < n && comp(first[child], first[child + 1]))
            ++child;                                  // the larger child
        if (!comp(first[root], first[child]))
            return;
        std::iter_swap(first + root, first + child);
        root = child;
    }
}

}  // namespace detail

// In place, O(n log n) worst case, not stable. comp(a, b) means "a goes
// before b"; the heap is a max-heap with respect to comp.
template <class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare comp = {})
{
    using Diff = typename std::iterator_traits<RandomIt>::difference_type;
    Diff n = last - first;
    for (Diff i = n / 2; i-- > 0; )                   // build the heap
        detail::sift_down(first, i, n, comp);
    for (Diff end = n; end > 1; --end) {              // extract the largest
        std::iter_swap(first, first + (end - 1));
        detail::sift_down(first, Diff{0}, end - 1, comp);
    }
}

#endif

// heap_demo.cpp - the generic heap sort, and the standard library's heap tools
#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include "heap_sort.hpp"

template <class Range>
void print(const char* label, const Range& r)
{
    std::cout << label;
    for (const auto& x : r) std::cout << ' ' << x;
    std::cout << '\n';
}

int main()
{
    std::vector<int> v{29, 10, 14, 37, 13, 5, 41, 22};
    heap_sort(v.begin(), v.end());
    print("heap_sort:        ", v);

    heap_sort(v.begin(), v.end(), std::greater<>{});
    print("descending:       ", v);

    std::vector<std::string> words{"pear", "fig", "apple", "kiwi", "date"};
    heap_sort(words.begin(), words.end());
    print("strings:          ", words);

    std::vector<int> w{29, 10, 14, 37, 13, 5, 41, 22};
    std::make_heap(w.begin(), w.end());               // the same max-heap layout
    print("std::make_heap:   ", w);
    std::sort_heap(w.begin(), w.end());
    print("std::sort_heap:   ", w);

    std::vector<int> k{29, 10, 14, 37, 13, 5, 41, 22};
    std::partial_sort(k.begin(), k.begin() + 3, k.end());   // three smallest, sorted
    std::cout << "partial_sort, 3:   " << k[0] << ' ' << k[1] << ' ' << k[2] << '\n';

    std::vector<int> q{29, 10, 14, 37, 13, 5, 41, 22};
    std::priority_queue<int> pq(q.begin(), q.end());      // a max-heap underneath
    std::cout << "priority_queue:   ";
    while (!pq.empty()) { std::cout << ' ' << pq.top(); pq.pop(); }
    std::cout << '\n';
    return 0;
}

Output (g++ 13.3 and clang++ 18.1.3 with libstdc++, identical):

heap_sort:         5 10 13 14 22 29 37 41
descending:        41 37 29 22 14 13 10 5
strings:           apple date fig kiwi pear
std::make_heap:    41 37 29 22 13 5 14 10
std::sort_heap:    5 10 13 14 22 29 37 41
partial_sort, 3:   5 10 13
priority_queue:    41 37 29 22 14 13 10 5

std::make_heap produced exactly the layout make_heap_down() produced in C, 41 37 29 22 13 5 14 10. The C++ standard requires a valid heap, not a particular one, so another standard library may print a different line there. std::sort_heap on that heap is the second half of heap sort. std::partial_sort finds the k smallest elements in order, which libstdc++ implements with a heap of size k, and std::priority_queue is a max-heap on a std::vector with push and pop in O(log n).

Java

// HeapSort.java - heap sort in Java 21
import java.util.Arrays;

public class HeapSort {

    // Max-heap in the array: children of i at 2i + 1 and 2i + 2. Not stable.
    static void heapSort(int[] a) {
        int n = a.length;
        for (int i = n / 2 - 1; i >= 0; i--)     // int index: i >= 0 is a real test
            siftDown(a, i, n);
        for (int end = n - 1; end > 0; end--) {
            int t = a[0]; a[0] = a[end]; a[end] = t;
            siftDown(a, 0, end);
        }
    }

    private static void siftDown(int[] a, int root, int n) {
        while (true) {
            int child = 2 * root + 1;
            if (child >= n)
                return;
            if (child + 1 < n && a[child] < a[child + 1])
                child++;
            if (a[root] >= a[child])
                return;
            int t = a[root]; a[root] = a[child]; a[child] = t;
            root = child;
        }
    }

    public static void main(String[] args) {
        int[] data = {29, 10, 14, 37, 13, 5, 41, 22};
        heapSort(data);
        System.out.println("Sorted: " + Arrays.toString(data));
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

Java has no unsigned int, so the i >= 0 loop that hangs in C with size_t is correct here. For a heap as a data structure, java.util.PriorityQueue is a min-heap by default.

Python

"""Heap sort in Python 3."""


def sift_down(a: list[int], root: int, n: int) -> None:
    """Move a[root] down the max-heap a[0:n] until neither child is larger."""
    while True:
        child = 2 * root + 1
        if child >= n:
            return
        if child + 1 < n and a[child] < a[child + 1]:
            child += 1
        if not a[root] < a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child


def heap_sort(a: list[int]) -> list[int]:
    """Sort list a in place. O(n log n) worst case, not stable."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)
    return a


if __name__ == "__main__":
    data = [29, 10, 14, 37, 13, 5, 41, 22]
    print("Sorted:", heap_sort(data))

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

The standard library’s heapq module maintains a min-heap in an ordinary list. heapq.heapify() on the example array gives [5, 10, 14, 22, 13, 29, 41, 37], and heapq.nsmallest(3, …) returns [5, 10, 13].

C#

// HeapSort.cs - heap sort in C#
namespace MyCPlus.Sorting;

public static class HeapSort
{
    // Max-heap in the array: children of i at 2i + 1 and 2i + 2. Not stable.
    public static void Sort(int[] a)
    {
        int n = a.Length;
        for (int i = n / 2 - 1; i >= 0; i--)
            SiftDown(a, i, n);
        for (int end = n - 1; end > 0; end--)
        {
            int t = a[0]; a[0] = a[end]; a[end] = t;
            SiftDown(a, 0, end);
        }
    }

    private static void SiftDown(int[] a, int root, int n)
    {
        while (true)
        {
            int child = 2 * root + 1;
            if (child >= n)
                return;
            if (child + 1 < n && a[child] < a[child + 1])
                child++;
            if (a[root] >= a[child])
                return;
            int t = a[root]; a[root] = a[child]; a[child] = t;
            root = child;
        }
    }
}

// Program.cs - sorts the article's array with HeapSort.Sort
using System;

namespace MyCPlus.Sorting;

public static class Program
{
    public static void Main()
    {
        int[] data = { 29, 10, 14, 37, 13, 5, 41, 22 };
        HeapSort.Sort(data);
        Console.WriteLine("Sorted: [" + string.Join(", ", data) + "]");
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

Where Heap Sort Is Used

In libstdc++ 13, std::sort‘s introsort loop calls __partial_sort, a heap sort, once the depth limit is reached. OpenJDK 21’s DualPivotQuicksort switches to its own heapSort when the recursion depth passes a limit.

Key Takeaways

• A heap is an array with an index rule. Children of i at 2i + 1 and 2i + 2 for 0-based arrays; the 1-based formula failed on 8.7% of random inputs while sorting the example correctly.
• Build the heap bottom-up. At most 2 comparisons per element, against up to 17.95 per element for repeated insertion on sorted input.
• Heap sort’s comparison count barely depends on the input: 217,379 to 244,460 for 10,000 values across four arrangements.
• Floyd’s variant saves about 41% of comparisons, which saved 8–14% of the time with GCC and nothing consistent with Clang for int values.
• Heap sort loses ground to quicksort as n grows: up to 1.5× slower up to a million elements, 1.7–2.1× at ten million on this machine.
• Index bugs in heap code fail quietly. An unsigned build loop hung with no sanitizer report; an off-by-one bound printed intact but unsorted output under GCC and pulled outside values into the array under Clang.

Frequently Asked Questions

Conclusion

Heap sort is the algorithm that makes every guarantee the others lack: in place, no recursion, no bad input. The measurements show what those guarantees cost. Its comparison count is almost constant, but its memory access pattern gets worse as arrays grow, so a sort that is 1.2 times slower than quicksort on small arrays is twice as slow on large ones. libstdc++ and OpenJDK both keep it as the fallback that guarantees the worst case, not as the algorithm they run first.

The heap itself outlives heap sort. Priority queues, top-k selection and schedulers all run on the same array layout and the same two operations, sift up and sift down. For the other algorithms in this series and how they compare, see the algorithms section.

Source Code and Tests

The C code is in mycplus/c-examples/sorting/heap-sort and the C++ code in mycplus/cpp-examples/sorting/heap-sort . The Java, Python and C# versions are in mycplus/java-examples/sorting/heap-sort, mycplus/python-examples/sorting/heap-sort and mycplus/csharp-examples/sorting/heap-sort, each with its own tests and workflow.

Build and test either one with:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the builds check on each change:

• Compilation with warnings as errors: GCC and Clang with -Wall -Wextra -pedantic -Werror (C11 and C17; C++17 and C++20), and MSVC with /W4 /WX.
• Correctness against a reference: both C sorts against qsort(), and both heap builds for the heap property, on 20,000 random arrays of 0 to 64 elements including empty arrays, INT_MIN, INT_MAX and heavy duplication; the C++ template against std::sort on 5,000 inputs, ascending and descending.
• The output on this page: the example, the trace, the count tables, the 1-based pitfall and its random search, and the C++ demo (with libstdc++) are compared with the output blocks above.
• Sanitizers: all tests run again under AddressSanitizer and UndefinedBehaviorSanitizer.
• The pitfalls: the build confirms that GCC warns about the unsigned build loop and that the program runs until stopped, and that AddressSanitizer reports the child <= n read.

The builds do not run the timing program, which depends on the machine. A green badge means the code compiles on those toolchains and passes those tests; it does not reproduce the timings above.