Insertion Sorting in C++ 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 &lt;vector&gt;

std::vector&lt;int&gt; ins_sort(std::vector&lt;int&gt; series)
{
    for(int i=1; i&lt;series.size(); i++)
    {
        int key = series[i];
        for(int j=i-1; j&gt;-1; j--)
        {
            if (key &lt; series[j])
            {
                series[j+1] = series[j];
                series[j] = key;
            }
            else break;
        }
    }
    return series;
}
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&lt;int&gt;::size vsize_t;
void ins_sort(std::vector&lt;int&gt; &amp; series)
{
    for(vsize_t i=1; i &lt; series.size(); i++)
    {
        insert(series, i, series[i]);
    }
}

void insert(std::vector&lt;int&gt; &amp; series, vsize_t last, int key)
{
    for (vsize_t j = last - 1; j &gt; -1; --j)
    {
        if (key &lt; 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&lt;int&gt; &amp; series, vsize_t last, int key)
{
    while ((--last &gt; -1) &amp;&amp; (key &lt; 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&lt;int&gt; &amp; series, vsize_t last, int key)
{
    while ((--last &gt; -1) &amp;&amp; (key &lt; 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&lt;int&gt; &amp; series, vsize_t last, int key)
{
    if (key &lt; series[0]) {
        while (last-- &gt; 0) {
            series[last+1] = series[last];
        }
    } else {
        while (key &lt; 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&lt;int&gt;::size vsize_t;
vsize_t unguarded_shift(std::vector&lt;int&gt; &amp; series, vsize_t last, int key)
{
    while (key &lt; series[last--])
    {
        series[last + 1] = series[last];
    }
    return last;
}

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


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



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