snippetcppModerate

Insertion Sorting in C++

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

insertionsortingstackoverflow

Problem

From Wikipedia:

Insertion sort iterates, consuming one input element each repetition,
and growing a sorted output list. Each iteration, insertion sort
removes one element from the input data, finds the location it belongs
within the sorted list, and inserts it there. It repeats until no
input elements remain.

Sorting is typically done in-place, by iterating up the array, growing
the sorted list behind it. At each array-position, it checks the value
there against the largest value in the sorted list (which happens to
be next to it, in the previous array-position checked). If larger, it
leaves the element in place and moves to the next. If smaller, it
finds the correct position within the sorted list, shifts all the
larger values up to make a space, and inserts into that correct
position.

Just tried out my solution in C++:

#include 

std::vector ins_sort(std::vector series)
{
    for(int i=1; i-1; j--)
        {
            if (key < series[j])
            {
                series[j+1] = series[j];
                series[j] = key;
            }
            else break;
        }
    }
    return series;
}

Solution

I wouldn't recommend passing and returning the vector by value. Pass by reference, and do not return at all - typically sorting is done in place anyway.

Another generic advice: no raw loops. The internal loop does some important job, which has to be realized and given a proper name, insert perhaps.

typedef std::vector::size vsize_t;
void ins_sort(std::vector & series)
{
    for(vsize_t i=1; i  & series, vsize_t last, int key)
{
    for (vsize_t j = last - 1; j > -1; --j)
    {
        if (key < series[j]) {
            series[j + 1] = series[j];
            series[j] = key;
        }
        else
            break;
    }
}

Now it is possible to simplify the logic by eliminating j, and combining the two condition checks together:

void insert(std::vector & series, vsize_t last, int key)
{
    while ((--last > -1) && (key < series[last]))
    {
        series[last + 1] = series[last];
        series[last] = key;
    }
}

You can see how the series[last] = key; assignment is rather redundant - it will necessarily be overwritten at the next iteration, so it only makes sense only at the last one:

void insert(std::vector & series, vsize_t last, int key)
{
    while ((--last > -1) && (key < series[last]))
    {
        series[last + 1] = series[last];
    }
    series[last] = key;
}

Testing two conditions at every iteration is expensive. You may notice that the first condition only strikes if key is less than all the elements, in other words, it is less than series[0] (it is sorted up to the point already):

void insert(std::vector & series, vsize_t last, int key)
{
    if (key  0) {
            series[last+1] = series[last];
        }
    } else {
        while (key < series[last])
        {
            series[last+1] = series[last];
        }
    }
    series[last] = key;
}

and applying the rule one more time, we see that the first loop does shift right by 1, and the second does unguarded shift right by one.

Combining everything, we are getting:

typedef std::vector::size vsize_t;
vsize_t unguarded_shift(std::vector & series, vsize_t last, int key)
{
    while (key  & series, vsize_t last)
{
    while (last-- > 0) {
        series[last+1] = series[last];
    }
    return last;
}

void insert(std::vector & series, vsize_t last, int key)
{
    if (key  & series)
{
    for(vsize_t i=1; i < series.size(); i++)
    {
        insert(series, i, series[i])
    }
}

Code Snippets

typedef std::vector<int>::size vsize_t;
void ins_sort(std::vector<int> & series)
{
    for(vsize_t i=1; i < series.size(); i++)
    {
        insert(series, i, series[i]);
    }
}

void insert(std::vector<int> & series, vsize_t last, int key)
{
    for (vsize_t j = last - 1; j > -1; --j)
    {
        if (key < series[j]) {
            series[j + 1] = series[j];
            series[j] = key;
        }
        else
            break;
    }
}

void insert(std::vector<int> & series, vsize_t last, int key)
{
    while ((--last > -1) && (key < series[last]))
    {
        series[last + 1] = series[last];
        series[last] = key;
    }
}

void insert(std::vector<int> & series, vsize_t last, int key)
{
    while ((--last > -1) && (key < series[last]))
    {
        series[last + 1] = series[last];
    }
    series[last] = key;
}

void insert(std::vector<int> & series, vsize_t last, int key)
{
    if (key < series[0]) {
        while (last-- > 0) {
            series[last+1] = series[last];
        }
    } else {
        while (key < series[last])
        {
            series[last+1] = series[last];
        }
    }
    series[last] = key;
}

typedef std::vector<int>::size vsize_t;
vsize_t unguarded_shift(std::vector<int> & series, vsize_t last, int key)
{
    while (key < series[last--])
    {
        series[last + 1] = series[last];
    }
    return last;
}

vsize_t shift(std::vector<int> & series, vsize_t last)
{
    while (last-- > 0) {
        series[last+1] = series[last];
    }
    return last;
}


void insert(std::vector<int> & series, vsize_t last, int key)
{
    if (key < series[0]) {
        last = shift(series, last);
    } else {
        last = unguarded_shift(series, last, key);
    }
    series[last] = key;
}



void ins_sort(std::vector<int> & series)
{
    for(vsize_t i=1; i < series.size(); i++)
    {
        insert(series, i, series[i])
    }
}

Context

StackExchange Code Review Q#47184, answer score: 14

Revisions (0)

No revisions yet.