Timing and counting comparisons

Why this matters

Suppose a teammate says "insertion sort is slow, use the other one". How would you check? You could run both sorts once and compare the times on your laptop. That answer is weak. The first run may have been slowed by something unrelated, such as a background program. The times depend on the machine, so a colleague with a different computer would get different numbers. And a single time does not tell you why one sort was faster.

This lesson gives you two better measurements. The first is a count. You add a counter to the sort and record how many comparisons and how many swaps it made. The count is the same on every machine, for the same input, so it tells you about the method itself. The second is a time. You measure the wall-clock time, which is the time you would see on a wall clock, and you take care to measure it in a fair way. The time tells you what a user would feel on a real machine.

The sorts themselves are covered in the earlier lessons of this module, such as bubble, selection and insertion sort, and the lesson on comparison contracts. This lesson does not explain how they work. It explains how to measure them and how to read the numbers.

Two different questions

A count answers the question "how much work did the sort do?" A time answers "how long did the computer take?" They are related but not the same.

A comparison is one moment where the sort asks whether one item is smaller than another. A swap is one moment where the sort exchanges two items in the vector. Both are cheap on their own, but a sort that does millions of them takes real time.

Here is a tiny example done by hand. Insertion sort works through the list from left to right. Each new item is moved left until it sits after every smaller item. Take the list 3 1 2.

The table has three comparisons and two swaps. The first comparison, 3 against 1, causes a swap. The second comparison, 3 against 2, causes a swap. The third comparison, 2 against 1, stops the move. A count gives you exactly these numbers, and you do not need to guess them.

The count does not say how long each step takes. A swap writes two values into memory. A comparison only reads them. In most sorts the swaps cost more than the comparisons, but the difference depends on the data type and on the machine. That is one reason a count alone can mislead, and the timing section returns to this point.

Example 1: counting comparisons and swaps in two sorts

The first program adds a counter to insertion sort and to selection sort. Each sort returns a small struct (a named group of values) that holds both counts.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
 
struct SortStats {
    std::size_t comparisons = 0;
    std::size_t swaps = 0;
};
 
SortStats insertion_sort(std::vector<int>& a) {
    SortStats s;
    for (std::size_t i = 1; i < a.size(); ++i) {
        std::size_t j = i;
        while (j > 0) {
            ++s.comparisons;
            if (a[j - 1] <= a[j]) {
                break;
            }
            std::swap(a[j - 1], a[j]);
            ++s.swaps;
            --j;
        }
    }
    return s;
}
 
SortStats selection_sort(std::vector<int>& a) {
    SortStats s;
    for (std::size_t i = 0; i + 1 < a.size(); ++i) {
        std::size_t smallest = i;
        for (std::size_t j = i + 1; j < a.size(); ++j) {
            ++s.comparisons;
            if (a[j] < a[smallest]) {
                smallest = j;
            }
        }
        if (smallest != i) {
            std::swap(a[i], a[smallest]);
            ++s.swaps;
        }
    }
    return s;
}
 
std::size_t std_sort_comparisons(std::vector<int>& a) {
    std::size_t comparisons = 0;
    std::sort(a.begin(), a.end(), [&comparisons](int x, int y) {
        ++comparisons;
        return x < y;
    });
    return comparisons;
}
 
int main() {
    std::vector<int> small{3, 1, 2};
    std::vector<int> a = small;
    SortStats ins = insertion_sort(a);
    std::cout << "insertion on 3 1 2: comparisons=" << ins.comparisons << " swaps=" << ins.swaps << '\n';
 
    std::vector<int> small2{2, 1, 3};
    std::vector<int> b = small2;
    SortStats sel = selection_sort(b);
    std::cout << "selection on 2 1 3: comparisons=" << sel.comparisons << " swaps=" << sel.swaps << '\n';
 
    const std::size_t n = 1000;
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(0, 1'000'000);
    std::vector<int> random_input(n);
    for (auto& x : random_input) x = dist(rng);
    std::vector<int> c = random_input;
    std::cout << "std::sort on random n=1000: comparisons=" << std_sort_comparisons(c)
              << " sorted=" << std::is_sorted(c.begin(), c.end()) << '\n';
}

Compile and run it:

g++ -std=c++20 -Wall -o stats stats.cpp
./stats

The output is:

insertion on 3 1 2: comparisons=3 swaps=2
selection on 2 1 3: comparisons=3 swaps=1
std::sort on random n=1000: comparisons=11697 sorted=1

The first two lines match the hand trace. Insertion sort made three comparisons and two swaps on 3 1 2. Selection sort on 2 1 3 made three comparisons, because it scans the rest of the list once for each position, and one swap, because only the first position needed to change.

The struct SortStats keeps the two counts together, so the caller gets both from one return value. The field starts at zero because of the = 0 after each name. Without that, a new struct could hold garbage numbers.

Counting the real sorts on a bigger list

The counts for a list of 1000 random numbers show the scale. Use the same kind of input for both sorts, so the numbers can be compared. The following program prints the counts for three kinds of input: random, already sorted, and sorted in reverse. Each row copies the input first, so every sort starts from the same data.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>
 
struct SortStats {
    std::size_t comparisons = 0;
    std::size_t swaps = 0;
};
 
SortStats insertion_sort(std::vector<int>& a) {
    SortStats s;
    for (std::size_t i = 1; i < a.size(); ++i) {
        std::size_t j = i;
        while (j > 0) {
            ++s.comparisons;
            if (a[j - 1] <= a[j]) {
                break;
            }
            std::swap(a[j - 1], a[j]);
            ++s.swaps;
            --j;
        }
    }
    return s;
}
 
SortStats selection_sort(std::vector<int>& a) {
    SortStats s;
    for (std::size_t i = 0; i + 1 < a.size(); ++i) {
        std::size_t smallest = i;
        for (std::size_t j = i + 1; j < a.size(); ++j) {
            ++s.comparisons;
            if (a[j] < a[smallest]) {
                smallest = j;
            }
        }
        if (smallest != i) {
            std::swap(a[i], a[smallest]);
            ++s.swaps;
        }
    }
    return s;
}
 
std::size_t std_sort_comparisons(std::vector<int>& a) {
    std::size_t comparisons = 0;
    std::sort(a.begin(), a.end(), [&comparisons](int x, int y) {
        ++comparisons;
        return x < y;
    });
    return comparisons;
}
 
std::vector<int> make_input(const std::string& kind, std::size_t n, std::mt19937& rng) {
    std::vector<int> v(n);
    if (kind == "random") {
        std::uniform_int_distribution<int> dist(0, 1'000'000);
        for (auto& x : v) x = dist(rng);
    } else if (kind == "sorted") {
        for (std::size_t i = 0; i < n; ++i) v[i] = static_cast<int>(i);
    } else {
        for (std::size_t i = 0; i < n; ++i) v[i] = static_cast<int>(n - i);
    }
    return v;
}
 
int main() {
    const std::size_t n = 1000;
    std::mt19937 rng(42);
    for (const std::string kind : {"random", "sorted", "reversed"}) {
        std::vector<int> base = make_input(kind, n, rng);
 
        std::vector<int> a = base;
        SortStats ins = insertion_sort(a);
        std::vector<int> b = base;
        SortStats sel = selection_sort(b);
        std::vector<int> c = base;
        std::size_t stdc = std_sort_comparisons(c);
 
        std::cout << kind << " n=" << n << '\n';
        std::cout << "  insertion: comparisons=" << ins.comparisons << " swaps=" << ins.swaps
                  << " sorted=" << std::is_sorted(a.begin(), a.end()) << '\n';
        std::cout << "  selection: comparisons=" << sel.comparisons << " swaps=" << sel.swaps
                  << " sorted=" << std::is_sorted(b.begin(), b.end()) << '\n';
        std::cout << "  std::sort: comparisons=" << stdc
                  << " sorted=" << std::is_sorted(c.begin(), c.end()) << '\n';
    }
}

The output is:

random n=1000
  insertion: comparisons=244208 swaps=243217 sorted=1
  selection: comparisons=499500 swaps=991 sorted=1
  std::sort: comparisons=11697 sorted=1
sorted n=1000
  insertion: comparisons=999 swaps=0 sorted=1
  selection: comparisons=499500 swaps=0 sorted=1
  std::sort: comparisons=10621 sorted=1
reversed n=1000
  insertion: comparisons=499500 swaps=499500 sorted=1
  selection: comparisons=499500 swaps=500 sorted=1
  std::sort: comparisons=8138 sorted=1

Read the numbers one row at a time. Several facts are visible.

Selection sort always makes the same number of comparisons, 499500, for 1000 items. It always scans the rest of the list, so the input order does not change the count. The number 499500 is 1000 times 999 divided by 2. Selection sort makes fewer swaps than insertion sort on random data, 991 against 243217, because it swaps at most once per position.

Insertion sort does very little work on sorted input. It made 999 comparisons and no swaps, because each new item was already in place and the inner loop stopped at once. On reversed input it does the most work it can, 499500 comparisons and 499500 swaps, because every new item has to move all the way to the front.

The std::sort counts are much smaller than either hand-written sort on random data. The count is about 11700 for 1000 items. For a list of length n, std::sort does about n times the base-2 logarithm of n comparisons on average, which for n equal to 1000 is about 10000. The count 11697 is in that range. The program does not print the exact formula, because the exact count depends on the implementation.

The std::sort count is for comparisons only. The standard library does its swaps and moves inside its own code, and the wrapper here cannot see them. That is why the program prints no swap count for std::sort. To count moves inside std::sort, you would need a custom element type that counts its own copies and moves, which is more work than this lesson needs.

Counting the lambda, not the sort

The counter for std::sort lives inside a lambda. The lambda captures comparisons by reference, which is written [&comparisons], and it increases the counter each time the sort calls it. The sort does not know the lambda is counting. From the sort's point of view, it is only a comparison function.

The counter adds a little work to every comparison. That is fine when you want counts, but it means a counted sort should not be used for timing. The timing section uses separate, uncounted functions.

Example 2: a larger count, to see how the work grows

The numbers for 1000 items are small enough to read. For a larger list the counts grow quickly, and a comparison of growth rates is clearer. The next table uses the same insertion and selection sorts on 20000 random numbers, made with std::mt19937 seeded with 42, as in the first example.

These counts come from the same algorithms as before, run on a random input of 20000 values. Insertion sort made about one hundred million comparisons and almost the same number of swaps. Selection sort made about two hundred million comparisons but only about twenty thousand swaps.

Insertion sort on reversed input of 20000 values made 199990000 comparisons and 199990000 swaps. This is the worst case for insertion sort, and the count is 20000 times 19999 divided by 2.

These numbers already hint at the timing result in the next section. Selection sort did twice as many comparisons as insertion sort, yet it does far fewer swaps. Whether that makes it faster depends on what a swap costs, so the next step is to time the two sorts.

Example 3: timing a sort with warm-up runs

To time a sort, you need a clock. The standard library gives you std::chrono::steady_clock. The word steady means the clock always moves forward at a fixed rate. Another clock, std::chrono::system_clock, follows the time of day and can jump when the computer updates its clock from the network. A jump in the middle of a measurement would give a false time, so timing code uses the steady clock.

The program below times three sorts on the same random input. It follows three rules that make the numbers more trustworthy.

First, each run starts from a fresh copy of the input. The copy is made before the clock starts, so the time does not include the copy. Without this, the second run would sort an already sorted list and look much faster.

Second, the program runs each sort a few times without timing, which are the warm-up runs. The first run of a program is often slower. The memory it uses has not been loaded into the processor's fast memory, and the processor may be running at a lower speed while it wakes up. Warm-up runs let these effects pass before the timed runs begin.

Third, the program reports the median of several timed runs, not one run and not an average. The median is the middle value after sorting the times. A single slow run, caused by a background task, does not change it much.

#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdlib>
#include <utility>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
 
void insertion_sort(std::vector<int>& a) {
    for (std::size_t i = 1; i < a.size(); ++i) {
        for (std::size_t j = i; j > 0 && a[j - 1] > a[j]; --j) {
            std::swap(a[j - 1], a[j]);
        }
    }
}
 
void selection_sort(std::vector<int>& a) {
    for (std::size_t i = 0; i + 1 < a.size(); ++i) {
        std::size_t smallest = i;
        for (std::size_t j = i + 1; j < a.size(); ++j) {
            if (a[j] < a[smallest]) {
                smallest = j;
            }
        }
        std::swap(a[i], a[smallest]);
    }
}
 
// Runs the sort warmups times without timing, then runs timed times and returns the median in ms.
template <typename SortFn>
double median_ms(SortFn sort_fn, const std::vector<int>& base, int warmups, int timed) {
    for (int i = 0; i < warmups; ++i) {
        std::vector<int> copy = base;
        sort_fn(copy);
    }
    std::vector<double> times;
    for (int i = 0; i < timed; ++i) {
        std::vector<int> copy = base;  // copy is made before the clock starts
        auto start = std::chrono::steady_clock::now();
        sort_fn(copy);
        auto stop = std::chrono::steady_clock::now();
        if (!std::is_sorted(copy.begin(), copy.end())) {
            std::cerr << "sort failed\n";
            std::exit(1);
        }
        times.push_back(std::chrono::duration<double, std::milli>(stop - start).count());
    }
    std::sort(times.begin(), times.end());
    return times[times.size() / 2];
}
 
int main() {
    const std::size_t n = 20000;
    std::mt19937 rng(7);
    std::uniform_int_distribution<int> dist(0, 1'000'000);
    std::vector<int> base(n);
    for (auto& x : base) x = dist(rng);
 
    std::cout << std::fixed << std::setprecision(2);
    std::cout << "n = " << n << ", random data, median of 5 timed runs after 2 warm-up runs\n";
    std::cout << "insertion sort: " << median_ms([](std::vector<int>& v) { insertion_sort(v); }, base, 2, 5) << " ms\n";
    std::cout << "selection sort: " << median_ms([](std::vector<int>& v) { selection_sort(v); }, base, 2, 5) << " ms\n";
    std::cout << "std::sort:      " << median_ms([](std::vector<int>& v) { std::sort(v.begin(), v.end()); }, base, 2, 5) << " ms\n";
}

Compile with optimisation turned on and run it:

g++ -std=c++20 -Wall -O2 -o timing2 timing2.cpp
./timing2

The output on the machine used for this lesson, a WSL2 Linux system with g++ 15.2.0, was:

n = 20000, random data, median of 5 timed runs after 2 warm-up runs
insertion sort: 580.86 ms
selection sort: 62.11 ms
std::sort:      0.66 ms

Your numbers will differ. The exact times depend on the processor, the other programs running, and the compiler. What should match is the order: std::sort is far faster than both hand-written sorts, and selection sort is faster than insertion sort on this input.

Reading the timing result against the count

Selection sort made about 200 million comparisons and only 20 thousand swaps. Insertion sort made about 100 million comparisons and 100 million swaps. Selection sort did twice as many comparisons, yet it ran about nine times faster.

This is the point where the count and the time disagree, and the reason is the cost of each operation. A comparison reads two values and decides, and it is cheap. A swap writes two values back into the vector, so it is more expensive, and insertion sort does a swap at almost every step on random data. Once the counts are known, the time can be explained. A count alone would have pointed the wrong way.

The lesson is not that comparisons are free. It is that a sort should be judged by the time it takes, with the count used to explain the time, not as a substitute for it.

Common mistakes

Mistake 1: timing one run

A single timed run is the most common error. The first run can be slower because of the warm-up effects described above, and a background task can make any single run slower. Running the sort several times and taking the median avoids both problems. The number of runs in this lesson, five timed runs after two warm-up runs, is small, so for a real study you would use more runs.

Mistake 2: timing the copy with the sort

If the program copies the input inside the timed region, the time includes the copy. For a 20000-item list the copy is fast, but it is still extra time, and it grows with n. In the program above the copy happens before start is read, and stop is read after the sort returns.

Mistake 3: sorting the same vector twice

If a program sorts the same vector twice without copying it, the second sort starts from a sorted list. The following program shows this. It sorts a list of 1000 random values with insertion sort two times in a row, and it counts the comparisons each time.

#include <cstddef>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
 
std::size_t insertion_comparisons(std::vector<int>& a) {
    std::size_t comparisons = 0;
    for (std::size_t i = 1; i < a.size(); ++i) {
        for (std::size_t j = i; j > 0; --j) {
            ++comparisons;
            if (a[j - 1] <= a[j]) break;
            std::swap(a[j - 1], a[j]);
        }
    }
    return comparisons;
}
 
int main() {
    std::mt19937 rng(7);
    std::uniform_int_distribution<int> dist(0, 1000000);
    std::vector<int> v(1000);
    for (auto& x : v) x = dist(rng);
    std::cout << "first run:  " << insertion_comparisons(v) << '\n';
    std::cout << "second run: " << insertion_comparisons(v) << '\n';
}

The output is:

first run:  245909
second run: 999

The second run made 999 comparisons, which is the best case for insertion sort. A timing or count taken from that second run would look far better than the sort really is. The fix is the one used in the timing program: copy the input for each run, and do the copy outside the measured part.

Mistake 4: timing a debug build

A build with optimisation turned off, which is the default when you run g++ without -O2, runs code much more slowly and in a different way. The times from the same program can change by a large factor. Here are the timing results from the program above, built once with -O2 and once with -O0, on the same machine:

-O2:
insertion sort: 580.86 ms
selection sort: 62.11 ms
std::sort:      0.66 ms
 
-O0:
insertion sort: 1414.93 ms
selection sort: 1706.88 ms
std::sort:      1.96 ms

At -O0, selection sort is slower than insertion sort, the reverse of the optimised result. Every sort in a comparison must use the same build settings, and the build should be optimised. The -O0 numbers describe the unoptimised code, not the sort itself. Use -O2 for timing, and report the flag in the notes.

Mistake 5: a missing include

The timing code needs the chrono header. If you forget it, g++ stops with an error. Here is a real error from g++ 15.2.0. It came from a program that called std::chrono::steady_clock::now() and did not include <chrono>:

nochrono.cpp: In function ‘int main()’:
nochrono.cpp:4:23: error: ‘std::chrono’ has not been declared
    4 |     auto start = std::chrono::steady_clock::now();
      |                       ^~~~~~

The message names the missing piece, std::chrono. The fix is to add #include <chrono> at the top of the file. Read the first line of the error to find the file and the line number, then read the words after error:.

Mistake 6: counting inside the timed code

The counted sorts in example 1 are not fit for timing. The counter adds work to every comparison, so the timed number would include the counting. Keep two versions of each sort: a counted one for the count, and a plain one for the timing. The timing program above uses plain versions for this reason.

Practice

Exercise 1. Trace insertion sort by hand on the list 2 3 1. Write down the number of comparisons and the number of swaps.

Show the answer

Start with 2 3 1. Take the 3: it compares with 2, which is in order, so it stops. That is one comparison and no swap. Take the 1: it compares with 3, not in order, so it swaps, giving 2 1 3. It compares with 2, not in order, so it swaps, giving 1 2 3. The first position is reached, so it stops. Totals: three comparisons and two swaps. The program form gives the same answer, which you can check by calling insertion_sort on 2 3 1.

Exercise 2. Trace selection sort by hand on the list 2 1 3. Write down the number of comparisons and the number of swaps.

Show the answer

For position 0, scan the other two items. Compare 1 with 2, and 1 is smaller, so the smallest is at index 1. Compare 3 with 1, which is not smaller. That is two comparisons. Swap the 2 and the 1, giving 1 2 3, which is one swap. For position 1, compare 3 with 2, which is not smaller. That is one comparison. The smallest is already in place, so there is no swap. Totals: three comparisons and one swap. This matches the output of the first program.

Exercise 3. Explain why insertion sort made 999 comparisons and no swaps on sorted input of 1000 values.

Show the answer

Each new item is compared once with the item before it. That item is smaller or equal, so the inner loop stops at once. Every item needs exactly one comparison, and there are 999 items after the first one, which gives 999 comparisons. No item moves, so there are no swaps.

Exercise 4. The timing program uses the median of five timed runs. Explain why the median is a better choice than the average when one run is unusually slow.

Show the answer

An average includes every value, so one slow run raises it. The median takes the middle value after sorting the times. With five times, the median is the third value, and one unusually slow run becomes the largest value and does not affect the middle. The median stays close to the typical run.

Exercise 5. Change the timing program so it also times insertion sort on reversed input of 20000 values. Predict whether it will take longer than on random input, and say why.

Show the answer

It will take longer. The reversed input forces every new item to move all the way to the front, so insertion sort makes 199990000 comparisons and 199990000 swaps, as the count table showed. On random input it made about 100 million of each. The timed result should be roughly twice as long, although the exact ratio depends on the machine. To make the change, build a reversed input the same way the counting program does, then pass it to median_ms in place of the random input.

Summary

• A count of comparisons and swaps is the same on every machine for the same input, so it compares the method itself.
• A time depends on the machine and must be measured carefully, with a steady clock, a fresh copy of the input before each run and the timing kept apart from the copy.
• Warm-up runs and the median of several timed runs make a time more reliable than a single run.
• Build with -O2 when timing, and use the same build for every sort you compare.
• A count explains a time but does not replace it. Selection sort did more comparisons than insertion sort on random data and still ran faster, because a swap costs more than a comparison.