# 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 <vector>

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

-
Judge me ! Please... –  matheussilvapb Apr 14 at 23:27

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<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;
}
}


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

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;
}
}


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<int> & 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<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;
}


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<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])
}
}

-
@Jamal I can't tame the formatting. Pleas attend. –  vnp Apr 15 at 0:08
Done. :-) Just indent each line of code by four spaces instead of using <code>. If done inside a numbered or bulleted list, it has to be eight spaces. –  Jamal Apr 15 at 1:02
And if you have indented code that needs another level, just place an x in column 1 of the first line, select all lines, hit Control + K, and remove the x. Formatting code just needs a non-whitespace character in column 1 to perform and indent by four spaces. –  David Harkness Apr 15 at 1:27
BTW, 200+ rep probably means it's time to choose a user name. Congrats! :) –  David Harkness Apr 15 at 1:30
Thank you for formatting help and for congratulations. –  vnp Apr 15 at 1:37

For the loop counter, use std::vector<int>::size_type instead of int. You cannot guarantee that an int will fit the vector's size, especially if you're sorting a lot of elements. It's also more proper in general to use std::size_type when looping through a storage container.

-

As far as style is concerned, I would recommend using something that makes maximum use of the Standard Library, e.g. the following code in C++11

template<class FwdIt, class Compare = std::less<typename std::iterator_traits<FwdIt>::value_type>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare())
{
for (auto it = first; it != last; ++it) {
auto const insertion = std::upper_bound(first, it, *it, cmp);
std::rotate(insertion, it, std::next(it));
}
}


Things to note compared to your own implementation:

• same signature as std::sort: two iterators and a comparison function object, this makes your algorithm usable with any container rather than just std::vector
• the comparison predicate used is std::less by default, but that can be changed by passing another function object or lambda expression: this makes your algorithm usable with more types and predicates
• use of standard algorithms
• it repeatedly finds the insertion point of the next element pointed to by it using a binary search std::upper_bound in the currently sorted sub-range [first, it). Maybe for short input sequences, an ordinary std::find would give better cache locality (something to be tested).
• it then inserts this element at the insertion point using the std::rotate algorithm
• the complexity is easy to reason about: an outer linear loop with an interior linear rotation, gives $O(N^2)$ complexity in the input range's length N == std::distance(first, last)

You could call it like this:

auto v = std::vector<int> { 4, 3, 2, 1 };
insertion_sort(begin(v), end(v)); // now 1, 2, 3, 4

-
@Jamal tnx for adding proper formula typesetting, I didn't know it was possible here, because it isn't on SO. –  TemplateRex Apr 16 at 20:02
It was enabled here just recently. I believe it's not on SO because if it's used on a lot of questions, it could really reduce performance. Anyway, to use MathJax, apply the \\$ delimiter. –  Jamal Apr 16 at 20:09