Insertion sort on nearly sorted data

Why this matters

Real data often arrives almost in order already. A list of exam scores is sorted by roll number, and one student's row was typed in the wrong place. A log file has timestamps that go up nearly every line, with a few lines written late. A playlist is in order except that one song was moved. Sorting this data from scratch wastes work, because most of the items are already where they belong.

Insertion sort is a simple sorting method that handles this case well. Its cost depends on how far the input is from sorted. On sorted input it does almost nothing. On reversed input it does the most work possible. This lesson counts the steps in the C++ code, explains why nearly sorted input is fast, and measures the difference on a list of 50,000 values.

The earlier lessons in this module covered bubble, selection and insertion sort on random data. This lesson looks at the same insertion sort from a different angle: how much work it does for a given input. Shell sort, later in the module, builds on this idea.

The idea: sorting a hand of cards

Imagine you pick up playing cards one at a time and keep them in your left hand in order. You take the next card from the table. You slide it left past every card that is bigger, until you reach a card that is smaller or until you reach the start of your hand. Then you put the card there.

Insertion sort does exactly this with the items of an array. The array is split into two parts. The left part, which starts with one item, is always in order. The right part holds the items not yet placed. Each step takes the first item of the right part and inserts it into the left part.

Here is the idea on the array 3 1 2. Each line shows the array after one step.

start:            3 1 2   left part is just "3"
take 1:           1 3 2   1 slid past 3, left part is "1 3"
take 2:           1 2 3   2 slid past 3, left part is "1 2 3"

After the second step the whole array is in order. The left part grows by one item on each step, and it is always sorted. That is the rule that makes the method correct: once a step finishes, the first few items of the array are in order among themselves.

Writing the sort in C++

Here is the code. It uses a std::vector<int>, the resizable array from the arrays module. It also counts two things, which the rest of the lesson relies on.

#include <cstddef>
#include <vector>
 
struct Counts {
    long long comparisons = 0;  // times two values were compared
    long long shifts = 0;       // times a value moved one slot to the right
};
 
Counts insertion_sort(std::vector<int>& a) {
    Counts c;
    for (std::size_t i = 1; i < a.size(); ++i) {
        int key = a[i];          // the value to insert
        std::size_t j = i;       // the slot it is moving into
        while (j > 0) {
            ++c.comparisons;
            if (a[j - 1] <= key) break;   // the value on the left is small enough
            a[j] = a[j - 1];              // slide the bigger value one slot right
            ++c.shifts;
            --j;
        }
        a[j] = key;              // drop the value into its slot
    }
    return c;
}

The outer loop picks each item in turn, starting at index 1. Index 0 is already a sorted left part by itself, so there is nothing to insert there. The variable key holds the item being inserted. The inner loop looks at the item just to its left. If that item is bigger than key, it moves one slot to the right and the inner loop checks the next item to the left. If that item is not bigger, or if there is no item left to check, the loop stops and key is written into the gap.

The function takes the vector by reference, written with &. That means it changes the caller's vector in place and does not make a copy. It returns the two counts in a small struct called Counts. A struct is a named group of values, and the fields are read with a dot, as in c.shifts.

Here is the example 3 1 2 traced through the code. The table shows the value of i, the value of key, and the total counts after each outer step.

The final array is 1 2 3, with 3 comparisons and 2 shifts.

Counting the steps

There are two kinds of work in the code.

A comparison is one check of a[j - 1] <= key. It answers the question "is the value on the left small enough to stop here?"

A shift is one move of a value one slot to the right, the line a[j] = a[j - 1].

Every shift happens because a check said the left value was too big. Every check either causes a shift or stops the inner loop. So the total number of comparisons is at most the number of shifts plus the number of outer steps, which is n - 1 for an array of n items. That is an exact upper bound, and it is easy to check on the examples below.

The shift count has a clean meaning. An inversion is a pair of values that are in the wrong order: a bigger value sits to the left of a smaller one. The array 3 1 2 has two inversions, the pair 3, 1 and the pair 3, 2. Each shift moves one value past one smaller value to its right, so it removes exactly one inversion. The sort ends with no inversions. So the number of shifts equals the number of inversions in the input, every time. You can count inversions without sorting anything, which makes the shift count predictable.

Here are four inputs of ten values each. The inversion count was found by checking every pair.

The sorted input takes n - 1 comparisons, which is 9 for ten values, and no shifts at all. The reversed input takes 45 shifts. That number is 10 * 9 / 2, the count of all pairs of ten values, because every pair is an inversion.

The one-value row shows the most important point for this lesson. A single item that is far out of place costs 9 shifts, one for each value it passes. The rest of the array costs almost nothing. Insertion sort pays for the distance each item travels, not for the size of the array.

Checking the count on bigger lists

The next program builds lists of 10, 100 and 1,000 values. It starts with the values in order, then swaps about one tenth as many pairs of nearby values. Each swap puts a value one to three places away from where it started. It then counts the inversions and runs the sort.

#include <cstddef>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
 
// insertion_sort and Counts as above
 
long long count_inversions(const std::vector<int>& a) {
    long long n = 0;
    for (std::size_t i = 0; i < a.size(); ++i)
        for (std::size_t j = i + 1; j < a.size(); ++j)
            if (a[i] > a[j]) ++n;
    return n;
}
 
std::vector<int> nearly_sorted(std::size_t n, std::size_t swaps, unsigned seed) {
    std::vector<int> a(n);
    for (std::size_t i = 0; i < n; ++i) a[i] = static_cast<int>(i);
    std::mt19937 rng(seed);
    for (std::size_t s = 0; s < swaps; ++s) {
        std::size_t i = rng() % (n - 4);
        std::size_t d = 1 + rng() % 3;   // 1 to 3 places away
        std::swap(a[i], a[i + d]);
    }
    return a;
}
 
int main() {
    for (std::size_t n : {10, 100, 1000}) {
        auto a = nearly_sorted(n, n / 10, 42);
        long long inv = count_inversions(a);
        Counts c = insertion_sort(a);
        std::cout << "  n=" << n << " inversions=" << inv
                  << " shifts=" << c.shifts
                  << " comparisons=" << c.comparisons << "\n";
    }
}

The std::mt19937 is a random number generator from the random header. Giving it the same seed, here 42, makes every run produce the same list, which is what you want when you compare results. The % operator gives the remainder after a division, so rng() % (n - 4) is a number from 0 to n - 5.

Compile and run it with the commands below. The -std=c++20 flag selects the C++20 standard, -Wall turns on the usual warnings, and the output file name comes after -o.

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

Output on g++ 15.2.0 (Ubuntu 15.2.0-16ubuntu1):

  n=10 inversions=5 shifts=5 comparisons=12
  n=100 inversions=26 shifts=26 comparisons=125
  n=1000 inversions=274 shifts=274 comparisons=1273

In every row the shift count equals the inversion count. The comparison count is a little more than the shift count, because each of the n - 1 outer steps adds one check that stops the loop, except when the key slides all the way to index 0 without a stopping check.

Why nearly sorted input is fast

Suppose every value is at most d places away from its final position. Take one value x, and look at the values to its left that are bigger than x. Each of those values must end up to the right of x, and each one started at most d places from its final spot. So they all have final spots in a short stretch just right of x, and that stretch holds at most about 2d - 1 of them. So each value causes at most about 2d - 1 shifts, and the total shift count is at most about (2d - 1) times n.

For a small d, that is a straight-line amount of work in n. Computer scientists write this as O(n), read as "order n", which means the time grows in step with the number of items. Random data is different. On random data a typical value is far from its final place, so the shifts add up to roughly n * n / 4, which grows much faster than n. Computer scientists write that as O(n²), read as "order n squared".

The bound is about the shift count, and the time follows the same pattern. Each comparison and each shift is a few machine instructions, so the total work is close to comparisons plus shifts.

Timing the two cases

The next program sorts two lists of 50,000 values. One is random, and one is nearly sorted in the same way as above, with 500 swaps. It copies each list before timing the sort, so the copy does not count in the measurement.

#include <chrono>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
 
// Counts, insertion_sort and nearly_sorted as above
 
int main() {
    const std::size_t n = 50000;
    std::vector<int> random_values(n);
    std::mt19937 rng(7);
    for (auto& x : random_values) x = static_cast<int>(rng() % 1000000);
    auto nearly = nearly_sorted(n, n / 100, 7);
 
    for (auto [label, data] : {std::pair{"random", random_values},
                               std::pair{"nearly sorted", nearly}}) {
        std::vector<int> work = data;             // copy outside the timer
        auto start = std::chrono::steady_clock::now();
        Counts c = insertion_sort(work);
        auto end = std::chrono::steady_clock::now();
        auto us = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "  " << label << ": comparisons=" << c.comparisons
                  << " shifts=" << c.shifts << " time_us=" << us << "\n";
    }
}

The steady_clock is a timer from the chrono header that only moves forward. The sort time is the difference between two readings. The for (auto [label, data] : ...) line loops over two pairs and unpacks each pair into two names. This form needs C++17 or later.

Compile it with optimisation turned on, using -O2. The -O2 flag asks the compiler to make the code faster. Without it the timing mostly measures the slow, unoptimised form of the code.

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

Output from one run on g++ 15.2.0 under WSL2 on this machine:

  random: comparisons=624806145 shifts=624756157 time_us=219153
  nearly sorted: comparisons=51563 shifts=1564 time_us=63

Timing numbers change from run to run and from machine to machine. Another run gave about 210 milliseconds for the random list and 117 microseconds for the nearly sorted list. The shape of the result stays the same: the random list took about 0.2 seconds, and the nearly sorted list took about 60 microseconds, which is about three thousand times faster. The random list needed about 625 million shifts. The nearly sorted list needed 1,564 shifts and 51,563 comparisons, and 51,563 is exactly 49,999 + 1,564, which is n - 1 plus the shifts, the bound from the counting section.

When you compile without -O2, the same program prints time_us=5647027 for the random list and time_us=692 for the nearly sorted one. The ratio is still about 8,000 to 1, but the absolute times are much bigger. Always state the compiler flags when you report a timing.

Step counts are the better measure

A timer tells you how long one run took on one machine. The step counts tell you how much work the algorithm does, and they are the same on every machine. When you compare two sorts or two inputs, report the comparisons and shifts first, then the time. The shift count in particular is a fixed property of the input: it is the number of inversions, and you can check it on paper.

Common mistakes

Missing the bound check

A common first mistake is to write the inner loop without the j > 0 test:

while (a[j - 1] > key) {   // no check that j > 0
    a[j] = a[j - 1];
    --j;
}

The test is needed because j is a std::size_t, which is an unsigned number. When j is 0, the expression j - 1 does not give -1. Unsigned arithmetic wraps around, so it gives the largest value of the type. The vector then reads far outside its memory. Standard C++ calls this undefined behaviour, which means the language makes no promise about what happens next. A program can print wrong numbers, crash, or appear to work.

To see the problem clearly, put the loop above in a function, call it on 3 1 2, and build with the library's safety checks turned on. The -D_GLIBCXX_ASSERTIONS flag adds these checks to the g++ standard library, at some cost in speed.

g++ -std=c++20 -Wall -O0 -D_GLIBCXX_ASSERTIONS -o bug_check bug_check.cpp
./bug_check
echo "exit status $?"

Output on g++ 15.2.0:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.
exit status 134

The program stops at once with exit status 134, which means it was ended by an abort signal. Without the flag the same program may print a wrong answer instead.

The important part is the last phrase, Assertion '__n < this->size()' failed. It says that an index was not smaller than the size of the vector. The first part of the line, the file name and the long template text, is less important. When you see this message, look for an index that can reach a value below 0 or past the end.

Forgetting the final store

The line a[j] = key; at the end of the outer loop is easy to lose. Without it the value in key is never written back, and some values are overwritten and lost. Here is the loop with that line removed, run on 3 1 2:

3 3 3

The array should be 1 2 3. The output has the value 3 three times, because the shifts copied 3 over the slots and the value 1 was never written in.

Expecting fast sorts on random data

Insertion sort is fast only when the input is nearly sorted. On the random list of 50,000 values above, it took about 0.2 seconds with -O2, and it would take about 16 times longer for 200,000 random values because the work grows with the square of the size. For large random data, use std::sort from the algorithm header, which the sorting lessons in this module compare with the methods covered here.

Counts that overflow int

The shift count grows like n * n / 4 for random data. For n equal to 100,000 that is about 2.5 billion, which is larger than the largest int, about 2.15 billion. The code above uses long long for both counts for this reason. A counter declared as int would overflow, and signed overflow is also undefined behaviour in C++.

Mixing signed and unsigned loop variables

A loop that compares an int index with a.size() gives a warning. The compiler reports it when -Wall is on:

warn_sign.cpp:4:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

The fix is to declare the index as std::size_t, as the code above does. Read every warning that -Wall prints, because this one often comes before a bug like the one in the bound check section.

Practice

Exercise 1. Trace 4 2 5 1 through the code. After each outer step, write the array, and give the total comparisons and shifts at the end.

Show the answer

Step i = 1, key 2: 4 is bigger, so it moves right. The array is 2 4 5 1. Comparisons 1, shifts 1. Step i = 2, key 5: 4 is not bigger, so the loop stops at once. The array is 2 4 5 1. Comparisons 2, shifts 1. Step i = 3, key 1: 5, 4 and 2 are each bigger, so all three move right, and the loop reaches index 0. The array is 1 2 4 5. Comparisons 2 + 3 = 5, shifts 1 + 3 = 4.

The final array is 1 2 4 5, with 5 comparisons and 4 shifts. The 4 shifts equal the inversions in 4 2 5 1: the pairs (4, 2), (4, 1), (2, 1) and (5, 1).

Exercise 2. Without running the code, predict the comparisons and shifts for 1 2 3 4 5 6 7 8 10 9. Then check your answer with the program.

Show the answer

Shifts: 1. The only inversion is the pair 10, 9. Comparisons: 10. Values 2 to 8 each need one comparison, which is 7 in total, one comparison for the key 10 against 8, and two comparisons for the key 9, one against 10 and one against 8. That totals 7 + 1 + 2 = 10. The program prints comparisons=10 shifts=1.

Exercise 3. How many comparisons and shifts does insertion sort use on a reversed list of six values?

Show the answer

Shifts: 15. Comparisons: 15. Every pair of the six values is an inversion, and there are 6 * 5 / 2 = 15 pairs. Each outer step has one comparison for every shift, because each key slides all the way to index 0 without a stopping check. The program prints comparisons=15 shifts=15 for 6 5 4 3 2 1.

Exercise 4. A list has 1,000 values, and each value is at most 2 places from its final position. Give an upper limit on the number of shifts.

Show the answer

About 3,000 shifts at most. With d = 2, the bound from the speed section is (2d - 1) * n = 3 * 1000 = 3000. This is an upper limit, so the real count can be smaller.

Exercise 5. Why does the timing program copy data into work before starting the timer, instead of sorting data directly?

Show the answer

Insertion sort changes the array it is given. If the program sorted data directly, the second run would start from an array that is already sorted, and its timing would be wrong. Copying each list into work before the timer starts gives every run the same unsorted input, and the copy itself is not counted in the time.

Summary

• Insertion sort keeps a sorted left part and slides each new value into its place.
• Each shift removes exactly one inversion, so the shift count equals the number of inversions in the input.
• On sorted or nearly sorted input the work grows with n, while on random input it grows with n squared.
• Count comparisons and shifts when you compare sorts, because they do not change between machines. Timings do.
• The j > 0 check prevents an unsigned index from wrapping past zero, and -D_GLIBCXX_ASSERTIONS helps find this kind of bug.
• Use long long for counts on large inputs, because the shift count can pass the range of int.