Sorting Algorithms in C and C++: Complexity, Stability and Measured Comparisons

On 10,000 values already in order, insertion sort made 9,999 comparisons and a quicksort that picks the last element as its pivot made 49,790,551. Shuffle the values inside each block of eight neighbors and bubble sort needed 79,876 comparisons; swap 100 random pairs instead and it needed 49,356,256. A complexity table gives the growth rate of each algorithm. It does not show that the same O(n²) label can mean ten thousand comparisons or fifty million, depending on how the input is arranged.

This page compares seven sorting algorithms and the C and C++ standard library sorts. It has a complexity and stability table, comparison counts on six input arrangements, and timings from two compilers. Each algorithm has its own article with a traced example, code in five languages and its own measurements, linked from its section below; the C code measured here is the code from those articles. Every program was compiled with GCC 13.3 and Clang 18.1.3 on Ubuntu 24.04 (C under -std=c11 and -std=c17; C++ under -std=c++20 and -std=c++23, and the short C++ example under -std=c++17 too), with -Wall -Wextra -pedantic and no warnings. The C tests also ran clean under GCC’s AddressSanitizer and UndefinedBehaviorSanitizer. Every output block is captured verbatim, and the code is in two GitHub repositories whose builds run the tests on each change.

The Short Answer

Which sorting algorithm is fastest? None on every input. For 1,000,000 random integers on the test machine, with either compiler, every run of std::sort, std::stable_sort, merge sort and both quicksorts finished in 54 to 106 ms, and every run of heap sort, Shell sort and qsort() took 101 to 155 ms. Within the faster group the order changed from run to run. On sorted input, insertion sort, bubble sort and merge sort with a skip-if-ordered check each made 9,999 comparisons on 10,000 elements; heap sort made 244,545.

Which sorting algorithms are stable? Insertion sort, bubble sort and merge sort, plus std::stable_sort. Selection sort, Shell sort, heap sort and quicksort are not. C’s qsort() makes no promise either way.

What should I use in real code? std::sort in C++, or std::stable_sort when equal elements must keep their order. In C, qsort() with a comparator that does not subtract.

What Is a Sorting Algorithm?

A sorting algorithm rearranges the elements of a sequence into order according to a comparison, such as ascending numeric value. Algorithms differ in how many comparisons and moves they make, in how much extra memory they need, and in whether they are stable: whether elements that compare equal keep their original relative order.

Every algorithm on this page is a comparison sort: it learns about the data only by asking whether one element should come before another. That puts a floor under the average case. A comparison sort needs about log₂(n!) comparisons, which grows as n log n, so O(n log n) is the best average a comparison sort can reach. Counting sort and radix sort avoid the floor by reading the keys directly, and are not covered here. The C standard library offers qsort(), and C++ offers std::sort and std::stable_sort, covered below.

Sorting Algorithm Comparison Table

A few of these entries depend on the implementation. Insertion sort’s and bubble sort’s O(n) best case applies only to already sorted input, and bubble sort needs an early exit to reach it. Merge sort reaches O(n) on sorted input only with a check that skips the merge when the two halves are already in order, as the version here has. Heap sort’s O(n log n) best case assumes distinct keys. Quicksort’s O(log n) stack assumes the recursion goes into the smaller partition, as the last-pivot version here does; the middle-pivot version uses plain recursion, which can reach O(n) depth. Merge sort’s O(n) is the size of the temporary buffer. Selection sort’s instability applies to the usual array version, which swaps the minimum into place.

How This Was Measured

No CPU pinning or frequency-scaling control was used, and no variance statistics beyond the ranges were captured. All timings come from this one virtual machine, so treat the ratios as indications for this machine rather than constants. The comparison counts do not depend on the machine: they are fixed by the code and the input, and a Windows build with Microsoft’s compiler reproduced every algorithm’s row exactly. A fixed-seed generator is used instead of rand() because rand() produces a different sequence on each C library (see generating random numbers in C and C++).

Comparisons on Six Kinds of Input

The counting program sorts 10,000 values in six arrangements and checks every result against qsort():

• sorted and reversed;
• random;
• local: sorted, then shuffled inside each block of eight, so no value is more than seven positions from its place;
• far swaps: sorted, then 100 pairs of random positions swapped, so only 200 values are out of place but many are thousands of positions away;
• 10 distinct: random values reduced to the ten numbers 0 to 9.

The first five are generated the same way and in the same order as in the insertion sort and merge sort articles, so the rows for those two algorithms match the counts printed there.

Output:

comparisons, n = 10000, MERGE_SKIP_SORTED = 1
algorithm                sorted    reversed      random       local   far swaps 10 distinct
insertion sort             9999    49995000    25193556       27735      820212    22705038
selection sort         49995000    49995000    49995000    49995000    49995000    49995000
bubble sort                9999    49995000    49921510       79876    49356256    49431497
shell sort (Knuth)        75243      120161      236528       87799      142042      110265
merge sort                 9999       79007      127152       65772       79514      122850
heap sort                244545      226687      235396      244391      244248      217761
quicksort (middle)       143654      143674      200544      152490      143915      165387
quicksort (last)       49790551    49822179      164900    16837669     2256065     5042178
qsort() glibc             64608       69034      120346       72573       94861      116401
every result matched a qsort() reference

Each row says something the complexity table cannot:

• Selection sort’s count matches the formula exactly. It always makes n(n − 1)/2 = 49,995,000 comparisons, because it scans the whole unsorted part to find each minimum whatever the input looks like. Its row is the same number six times.
• Insertion sort pays for distance, not for the number of misplaced elements. The local input cost 27,735 comparisons. The far-swaps input, with only 200 values out of place, cost 820,212: its 810,213 inversions (pairs in the wrong order) plus n − 1. The insertion sort article counts the inversions separately and shows that the moves equal them exactly.
• Bubble sort handled the local input and failed on far swaps. A small value swapped far toward the back moves forward only one position per pass, so 100 swapped pairs pushed bubble sort to 49,356,256 comparisons, 98.7% of its worst case, while the local input cost 79,876. The bubble sort article traces this effect with a single misplaced value.
• The pivot choice decides quicksort’s worst case. With a middle pivot, sorted and reversed input were cheaper than random. With a last-element pivot, the same inputs cost 49,790,551 and 49,822,179 comparisons, about 350 times more. The local input cost it 16,837,669, against insertion sort’s 27,735: in that input the last value of a range tends to sit close to the range’s largest, so most partitions split off only a few elements. The quicksort article measures the same failure and the recursion depth it causes.
• Merge sort’s skip check is a trade. The version here skips a merge when the two halves are already in order, which took sorted input down to 9,999 comparisons and added 6,806 on random input. The merge sort article measures the trade on each input.
• Heap sort is the least sensitive to input of the O(n log n) sorts. It stayed between 217,761 and 244,545 comparisons on every arrangement, a spread of 12%. It gains nothing from sorted input and loses little on bad input; the heap sort article splits its count between building the heap and sorting.
• glibc’s qsort() made exactly the same number of comparisons as this merge sort with the skip check turned off, on all six inputs. The repository builds the counting program a second time with -DMERGE_SKIP_SORTED=0, and the merge sort row becomes:

merge sort                64608       69034      120346       72573       94861      116401

That fits glibc’s own history: for release 2.39, a change that replaced its merge sort with introsort was reverted, because the switch made qsort() unstable and existing programs depended on stable behavior. The identical counts are consistent with the merge sort still being in place on this machine. They do not prove it.

Other C libraries use other algorithms. Built with Microsoft’s compiler (MSVC 19.44, Windows build 10.0.26200), every algorithm row in the table above came out identical, digit for digit, in both builds of the counting program, and only the qsort() row changed:

qsort() libc             125815      125813      151579      135360      126423       53918

Microsoft’s qsort() made nearly twice as many comparisons as glibc’s on sorted and reversed input (125,815 against 64,608, and 125,813 against 69,034), but fewer than half as many on the ten-distinct-values input (53,918 against 116,401). GitHub’s Windows runner, with MSVC 19.51, printed the same six numbers. Which algorithm Microsoft’s runtime uses was not checked against its source, so this page reports only the counts.

Which Sorting Algorithms Are Stable?

A sort is stable when elements that compare equal come out in the same relative order they went in. It matters when you sort records by one field after sorting by another: sort employees by name, then stable-sort by department, and each department’s list stays alphabetical.

The stability program gives each of 1,000 values a key from 0 to 9 and records its original position in the same int, as key * 10000 + position. The comparison macro is redefined to compare only the key, (x) / 10000 < (y) / 10000. A stable sort must therefore leave the positions of equal keys in ascending order:

Output:

algorithm            equal keys kept in input order?
insertion sort       yes
selection sort       no
bubble sort          yes
shell sort (Knuth)   no
merge sort           yes
heap sort            no
quicksort (middle)   no
quicksort (last)     no
qsort() glibc        yes

A “yes” is evidence from one input, not a proof; an unstable algorithm can preserve order by chance. Each “no” is a concrete counterexample. The results match what the algorithms do. Insertion and bubble sort move an element past a neighbor only when it is strictly smaller. The merge step takes from the right-hand run only when that element is strictly smaller. Selection sort, Shell sort, heap sort and quicksort all move elements across long distances, jumping them past equal values. The qsort() “yes” belongs to glibc: built with MSVC on Windows (19.44 on a desktop machine and 19.51 on GitHub’s runner), the same program printed “no” for qsort().

Timings: GCC, Clang and the Library

One run of the timing program built with GCC:

Output:

algorithm (ms)            n = 20000    n = 1000000
insertion sort                47.98              -
selection sort               445.38              -
bubble sort                 1006.20              -
shell sort (Knuth)             1.73         147.07
merge sort                     1.32         105.83
heap sort                      1.84         136.89
quicksort (middle)             1.31          87.97
quicksort (last)               1.12          61.81
qsort() glibc                  1.46         154.58

Across three runs per compiler, the medians fell in these ranges (milliseconds, random input):

Three results stand out:

• The compiler changed the O(n²) timings by up to about 5×. The same selection_sort source took 435–445 ms with GCC and 86.1–89.0 ms with Clang. The selection sort article, which measured a gap of about 4.5× in its own program, traces it to one conditional-move instruction in GCC’s inner loop. Bubble sort was about 3× slower with GCC, and the bubble sort article traces that to one vectorization pass. Insertion sort’s ranges overlapped, so this program shows no consistent difference for it. A hand-written inner loop can land well or badly on a particular compiler, so measure it on the compiler you ship with.
• qsort() was slower than a merge sort making more comparisons. On the random 10,000-element input, the merge sort with its skip check made 127,152 comparisons and qsort() made 120,346. At 1,000,000 elements the merge sort still took 84–106 ms with GCC and 66–68 ms with Clang, against 127–155 ms for qsort(). The likeliest cost is that qsort() calls the comparator through a function pointer for every comparison, while the merge sort is compiled with an inlined <. That is an inference; no profiler was run.
• Quicksort with a last-element pivot was the fastest C function on random data with GCC, and level with merge sort under Clang. It took 55–78 ms at a million elements and made fewer comparisons on random input than the middle-pivot version (164,900 against 200,544). Its weakness appears only on the sorted, reversed, local, far-swaps and duplicate-heavy inputs in the comparison table, which is how it survives testing on random data.

The Seven Algorithms in Brief

All eight functions (quicksort appears twice, with two pivot choices) are in one C source file, copied from the algorithms’ own articles. Every comparison goes through SORT_LESS(x, y), meaning “x sorts before y”. It is plain < by default, and the counting and stability programs redefine it. The header:

/* sorting.h - seven sorting algorithms (eight functions) for int arrays, in C11 */
#ifndef SORTING_H
#define SORTING_H

#include <stddef.h>

void insertion_sort(int a[], size_t n);
void selection_sort(int a[], size_t n);
void bubble_sort(int a[], size_t n);
void shell_sort(int a[], size_t n);
int  merge_sort(int a[], size_t n);      /* returns -1 if malloc fails */
void heap_sort(int a[], size_t n);
void quick_sort(int a[], size_t n);      /* Hoare, middle pivot; heap_sort above INT_MAX */
void quick_sort_last(int a[], size_t n); /* Lomuto, last pivot; heap_sort above INT_MAX */

#endif

Insertion Sort

Insertion sort takes each element in turn and shifts larger elements in the sorted prefix one place right until it finds the element’s position. It moves an element once per inversion, so its cost follows how far elements are from home: 27,735 comparisons on the local input, 25,193,556 on random. Library sorts use it as a finishing step for the same reason: libstdc++’s std::sort stops partitioning once a range is 16 elements or fewer, then runs insertion sort over the whole array, which by then is nearly sorted. The insertion sort article traces it step by step, measures the inversion count on five inputs and covers binary insertion sort.

Selection Sort

Selection sort finds the minimum of the unsorted part and swaps it to the front, repeating until one element remains. It makes n(n − 1)/2 comparisons on every input but at most n − 1 swaps. That bound on writes is its one advantage, and it matters only when writing an element costs far more than comparing two. The swap is also what makes it unstable: exchanging a[i] with a minimum further along can carry a[i] past an equal element. The selection sort article predicts the swap count, shows a stable variant and explains GCC’s slowdown from the compiled assembly.

Bubble Sort

Bubble sort swaps neighboring elements that are out of order and repeats until a pass makes no swaps. With an early exit it is O(n) on sorted input; without one it is O(n²) on every input. It is stable when the comparison is strict. On the far-swaps input it made 49,356,256 comparisons, almost as many as selection sort, which ignores the input entirely. That is why it rarely appears outside teaching. The bubble sort article has a pass-by-pass trace, a C++ version that sorts a std::forward_list, and four loop-bound bugs that compile without warnings.

Shell Sort

Shell sort runs insertion sort over elements a fixed gap apart, then shrinks the gap until a final pass with gap 1. The early passes move elements long distances cheaply, so the last pass runs on nearly sorted data, the case insertion sort handles well. The version measured here uses Knuth’s gaps 1, 4, 13, 40, and so on, and made 142,042 comparisons on the far-swaps input that cost insertion sort 820,212. It needs no recursion and no extra memory, and its complexity depends on the gap sequence. The Shell sort article compares eight gap sequences and has code in five languages.

Merge Sort

Merge sort splits the array in half, sorts each half recursively and merges the two sorted halves through a temporary buffer. It makes O(n log n) comparisons on every input, is stable, and needs O(n) extra memory. Stability comes from one comparison: on a tie the merge takes the left element first. It suits linked lists and external sorting, where data is read in sequence, and libstdc++’s std::stable_sort is a merge sort that uses a temporary buffer when it can allocate one. The merge sort article covers top-down, bottom-up and linked-list versions, counts inversions with the merge, and shows four mistakes that compile.

Heap Sort

Heap sort arranges the array as a binary max-heap, in which each element is at least as large as its children, then repeatedly swaps the largest element to the back and restores the heap in the part that remains. It has an O(n log n) worst case with O(1) extra memory and no recursion, a combination neither quicksort nor merge sort offers. That is why introsort, the algorithm behind libstdc++’s std::sort, switches to heap sort when quicksort’s recursion goes too deep. Its jumps between parent and child make poor use of the cache, and at a million elements it was slower than quicksort and merge sort. The heap sort article shows how the heap lives in an array, compares two ways to build it, and times Floyd’s variant.

Quicksort

Quicksort picks a pivot, partitions the array into elements smaller and larger than it, and sorts the two parts. It averages O(n log n) and was among the fastest here, but it is O(n²) when the pivot keeps landing at one end, as the last-element row of the comparison table shows. Both versions come from the quicksort article: Hoare partitioning with a middle pivot and plain recursion, and Lomuto partitioning with a last-element pivot that recurses into the smaller part to bound the stack. The quicksort article compares the two partition schemes, measures pivot strategies, and reproduces the stack overflow that plain recursion causes on 200,000 sorted elements.

Sorting in C and C++ Programs: qsort, std::sort and std::stable_sort

In application code, call the library. Here is what each one guarantees:

The C standard does not specify qsort()‘s algorithm, its complexity or its stability: cppreference notes that neither C nor POSIX require quicksort or any complexity or stability guarantee. In C, pass it a comparator that returns (a > b) - (a < b). The common return a - b; overflows when the values have opposite signs and large magnitudes; the bubble sort article shows it misordering INT_MIN and INT_MAX.

In C++, std::sort and std::stable_sort sort a std::vector or any random-access range in place. This program sorts 1,000 employee records by department and prints the first five names in department 0, which were created in ascending order:

// stable_vs_sort.cpp - what std::sort does to equal keys, and what
// std::stable_sort does instead. 1,000 records, 10 departments.
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

struct Employee {
    std::string name;   // e0, e1, ... in input order
    int dept;
};

static void show(const char* label, const std::vector<Employee>& v)
{
    std::cout << label;
    int shown = 0;
    for (const auto& e : v)                 // the first five in department 0
        if (e.dept == 0 && shown++ < 5)
            std::cout << ' ' << e.name;
    std::cout << '\n';
}

int main()
{
    std::uint64_t xs = 88172645463325252ULL;
    std::vector<Employee> staff;
    for (int i = 0; i < 1000; ++i) {
        xs ^= xs << 13; xs ^= xs >> 7; xs ^= xs << 17;
        staff.push_back({"e" + std::to_string(i), static_cast<int>(xs % 10)});
    }
    auto by_dept = [](const Employee& a, const Employee& b) { return a.dept < b.dept; };

    auto a = staff, b = staff;
    std::sort(a.begin(), a.end(), by_dept);
    std::stable_sort(b.begin(), b.end(), by_dept);

    show("input order:      ", staff);
    show("std::sort:        ", a);
    show("std::stable_sort: ", b);
    return 0;
}

Output (GCC 13.3 and Clang 18.1.3 with libstdc++, identical):

input order:       e26 e33 e41 e46 e59
std::sort:         e730 e341 e902 e664 e106
std::stable_sort:  e26 e33 e41 e46 e59

std::sort returned department 0 in an order unrelated to the input, and std::stable_sort kept it. Which order std::sort produces for equal keys depends on the library implementation, so other standard libraries will print a different second line. The repository’s comparison program measured the three functions on the same data. Its random 10,000-element array comes from a different stretch of the generator’s sequence than the C table’s, so its qsort() count differs slightly from the one above:

Output:

comparisons, n = 10000        random    sorted  reversed
std::sort                   161246    166608    122131
std::stable_sort            127592     73534     59141
qsort                       120528     64608     69024

equal keys kept in input order (1,000 records, 10 keys):
  std::sort        no
  std::stable_sort yes

milliseconds, n = 1000000 random, median of 5
  std::sort             71.47
  std::ranges::sort     69.16
  std::stable_sort      89.96
  qsort                131.59

std::sort and std::ranges::sort took about half as long as qsort() on the same million integers. Across four runs with g++, std::sort medians ranged from 54 to 82 ms and qsort() from 132 to 148 ms. The gap is not in the number of comparisons: qsort() made the fewest of the three on random input. The difference is again consistent with the per-comparison function-pointer call, since std::sort is a template and the compiler inlines the comparison. std::stable_sort varied with the compiler: 89–91 ms over four runs with g++ and 68 ms in all three runs with clang++, both using the same libstdc++.

A Comparator That Breaks std::sort

std::sort requires a comparator that is a strict weak ordering. In particular, comp(a, a) must be false. Passing <= violates that, and the result is undefined behavior:

// lte_comparator.cpp - std::sort with <= instead of < (undefined behavior)
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v(100, 7);                    // 100 equal values
    std::sort(v.begin(), v.end(),
              [](int a, int b) { return a <= b; }); // not a strict weak ordering
    std::cout << "sorted " << v.size() << " values\n";
    return 0;
}

Built with g++ -std=c++20 -O2, the program printed sorted 100 values and exited with status 0. That output looks correct. Built with AddressSanitizer, the same source reported a read past the end of the vector’s buffer, inside libstdc++’s partition loop:

==2020==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x5140000001d0 at pc 0x56308f13cc63 bp 0x7ffcd2ab2b70 sp 0x7ffcd2ab2b60
READ of size 4 at 0x5140000001d0 thread T0
    #0 0x56308f13cc62 in operator()<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, __gnu_cxx::__normal_iterator<int*, std::vector<int> > > /usr/include/c++/13/bits/predefined_ops.h:158
    #1 0x56308f13cc62 in __unguarded_partition<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> > > /usr/include/c++/13/bits/stl_algo.h:1877
    #2 0x56308f13cc62 in __unguarded_partition_pivot<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> > > /usr/include/c++/13/bits/stl_algo.h:1899
    #3 0x56308f13cc62 in __introsort_loop<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, long int, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> > > /usr/include/c++/13/bits/stl_algo.h:1931

Built with -D_GLIBCXX_DEBUG, libstdc++’s debug mode checked the comparator and aborted with status 134:

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

The partition loop stops scanning when comp returns false. With <= on equal values it never returns false, so the scan runs past the end of the array. The fix is a < b. For descending order, use std::greater<>{} or a > b, never >=. For comparators you write yourself, a debug-mode build is a cheap check to add to a test suite.

Choosing a Sorting Algorithm

For most programs the choice is the library, and the remaining question is whether you need stability. Writing your own sort is worth it when there is no library to call or its guarantees do not fit: firmware without malloc(), a hard bound on stack depth, or data whose shape you know, such as input in which every element starts close to its final position. The comparison counts above give the evidence for each row in the figure. Sorting is also a building block inside other algorithms: Kruskal’s algorithm begins by sorting a graph’s edges by weight, and the top 10 algorithms every programmer should know puts sorting first among the algorithm families it covers.

Key Takeaways

• The same complexity class can mean very different costs. Insertion sort, an O(n²) algorithm, made 9,999 comparisons on sorted input and 49,995,000 on reversed input.
• “Nearly sorted” needs a definition. Insertion sort made 27,735 comparisons when every value was within seven positions of home and 820,212 when 100 swaps moved values thousands of positions. Bubble sort made 79,876 and 49.4 million on the same two inputs.
• Stability comes from the implementation. Insertion, bubble and merge sort are stable when the comparison is strict. Selection, Shell, heap sort and quicksort are not, and C’s qsort() guarantees nothing.
• A last-element pivot fails on more than sorted input. It made 16.8 million comparisons on the locally shuffled input that insertion sort finished in 27,735.
• Heap sort gives a guarantee, not speed. Its comparison count varied by 12% across the six inputs, which is why introsort uses it as a fallback, but it was slower than quicksort and merge sort at a million elements.
• In C++, use std::sort or std::stable_sort. On this machine std::sort took about half as long as qsort() on a million integers, although qsort() made fewer comparisons.
• A comparator must be a strict ordering. <= in std::sort printed a normal result in an optimized build while AddressSanitizer reported an out-of-bounds read.
• Measure on your compiler. GCC and Clang differed by about 5× on the same selection sort source.

Frequently Asked Questions

Conclusion

Sorting algorithms are usually taught in the order of the complexity table, as if a better growth rate settled the question. The measurements here point the other way: the arrangement of the input, the choice of pivot, the strictness of one comparison and even the compiler changed the outcome more than the table predicted. Insertion sort matched the lowest count of any sort on sorted input and lost to every O(n log n) sort but the last-pivot quicksort once a hundred elements had moved far, and heap sort’s guarantee left it slower than both quicksorts at a million elements.

That makes the implementations worth writing once, instrumenting and breaking on purpose, and then replacing with the library call in production code. The algorithms section continues from here into searching, graphs and the algorithms that sorting makes possible.

Source Code and Tests

The C code is in mycplus/c-examples/sorting/sorting-algorithms and the C++ code in mycplus/cpp-examples/sorting/library-sorts . The insertion, selection, bubble, merge and heap sort articles each have their own folder beside sorting-algorithms/ in the same repositories, with the examples, tests and pitfalls from those articles.

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++20 and C++23), and MSVC with /W4 /WX.
• The same code as the articles: a script compares the insertion, selection, bubble, merge and heap sort functions in sorting.c with the ones in the per-article folders, character for character apart from the comparison macro, and fails if they drift apart.
• Correctness against a reference: all eight C functions against qsort() on 20,000 random arrays of 0 to 64 elements, including empty arrays, INT_MIN, INT_MAX and heavy duplication. std::stable_sort and std::ranges::sort are checked against a (key, position) reference on 5,000 random inputs.
• The printed output on this page: both builds of the comparison-count table, the stability table and the C++ std::sort example are compared byte for byte with the output blocks above. The qsort() row is compared only where the C library is glibc, because other libraries use other algorithms: with MSVC on Windows it made 151,579 comparisons on the random input and did not keep equal keys in order. The C++ example is checked only with libstdc++, because where std::sort puts equal keys varies between libraries.
• Sanitizers: the C tests run under AddressSanitizer and UndefinedBehaviorSanitizer. The byte-exact count checks are skipped there, because AddressSanitizer wraps qsort() and adds n − 1 comparator calls to its row. The C++ build confirms that the <= comparator is rejected by libstdc++ debug mode and reported by AddressSanitizer.

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