Insertion Sort in C++
This is not C++, yet. Just using std::cout does not C++ make. But do not fret, we'll get there.



Safe interface

Whenever designing an API (or interface), you should strive to make it as safe as possible.

Your interface here is not safe: having two un-linked variables to correctly pass is asking for troubles; it is just too easy to mix the variables up and pass a size that does not correspond to the array to be sorted (or printed).

Obviously, in your toy example it does not show up, however as soon as you manipulate multiple arrays in the same function you'll be very likely to make this mistake. And even with a single array, passing the length before re-allocating (for example) is also likely.

So, you need to aim for an interface that conveys both pieces of information in a single argument. An obvious choice is std::vector, another would be some instance of array_view or a random_access_range but those are not Standard so let's not bother for now.

Thus, the interface becomes:

void insertion_sort(std::vector&lt;int&gt;&amp; array);
void print(std::vector&lt;int&gt; const&amp; array);


Do note the consistency in the naming; both times the argument is named array instead of being once arr and once array. Consistency may be the hobgobelin of little minds, but it does help readers.



Algorithmic

An insertion sort is generally described simply as: read each element in turn, and insert it in the right position among the previous read (and sorted) elements.

The cost of the algorithm is thus:


for each of the N elements
the cost of inserting it in the i-1 (where i is the index of the element being read) first elements


The outer loop we cannot do anything about, but what of the insertion?

In your code, the insertion is done by:

    while (j &gt; 0 &amp;&amp; arr[j - 1] &gt; arr[j]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
        j--;
    }


That is, the value is bubbling up toward the front until it finds its spot.

This is suboptimal in terms of comparisons: the optimal algorithm to find the position to insert is using a binary search rather than a linear search, for O(log N) complexity rather than O(N) one.

In terms of number of moves, well, you may have to move all elements, so it could only be improved by a constant factor anyway.

Standing on the shoulders of giants, we can improve the code by separating the search and the move, and use pre-existing algorithms to do so:


std::upper_bound yields a pointer to the first element in the range that is greater than the value we search with
std::rotate rotates the elements of the range (and middle point) passed to it, such that the range delimited by the last two elements come to precede the range delimited by the first two


We can use them keeping to indices, although it is slightly verbose:

void insertion_sort(std::vector&lt;int&gt;&amp; array) {
    typedef std::vector&lt;int&gt;::iterator It;

    for (size_t i = 1, length = array.size(); i &lt; length; ++i) {
        // 1. Search
        It const end_sorted = array.begin() + i;
        It const insertion_point =
            std::upper_bound(array.begin(), end_sorted, array[i]);

        // 2. Insert
        std::rotate(insertion_point, end_sorted, end_sorted + 1);
    }
}


Thus I advise jumping the gun and just switch to iterators since that it what the interfaces of the algorithms we use consume:

void insertion_sort(std::vector&lt;int&gt;&amp; array) {
    typedef std::vector&lt;int&gt;::iterator It;

    for (It it = array.begin(), end = array.end(); it != end; ++it) {
        // 1. Search
        It const insertion_point =
            std::upper_bound(array.begin(), it, *it);

        // 2. Insert
        std::rotate(insertion_point, it, it + 1);
    }
}


Which in modern C++ would use auto rather than explicitly naming the iterator type:

void insertion_sort(std::vector&lt;int&gt;&amp; array) {
    for (auto it = array.begin(), end = array.end(); it != end; ++it) {
        // 1. Search
        auto const insertion_point =
            std::upper_bound(array.begin(), it, *it);

        // 2. Insert
        std::rotate(insertion_point, it, it + 1);
    }
}


Note that abbreviating further is not a good idea; while one-liners may give the writer a fuzzy warm feeling, they just end up being head scratchers for maintainers:

// Puzzle time!
void insertion_sort(std::vector&lt;int&gt;&amp; array) {
    for (auto it = array.begin(), end = array.end(); it != end; ++it) {
        std::rotate(std::upper_bound(array.begin(), it, *it), it, it + 1);
    }
}




What does endl do?

Finally, a trick question: what do think std::endl is and does?

std::endl is a so called stream manipulator, it is a function whose signature is:

template&lt; class CharT, class Traits &gt;
std::basic_ostream&lt;CharT, Traits&gt;&amp; endl( std::basic_ostream&lt;CharT, Traits&gt;&amp; os );


So, when used on a stream, it does an operation on said stream and returns it (to allow further chaining).

Specifically, ostream &lt;&lt; std::endl is equivalent to:

ostream &lt;&lt; '\n';
ostream.flush();


Where flush makes sure that the data is not buffered in the process but fully sent to the Operating System (it does not guarantee that the data is on disk, sent over the network, or anything else).

There is very little reason to call flush in general:


in the absence of guarantee that the data arrived on disk (or wherever), it serves not practical purpose
the buffer was introduced for performance reasons, bypassing it is asking to go slow


So, not only should you generally avoid flush, std::endl is a mouthful. Just write '\n' to get an end-of-line character and be done with it.

Thus, we rewrite print:

void print(std::vector&lt;int&gt; const&amp; array) {
    for (auto it = array.begin(), end = array.end(); it != end; ++i) {
        std::cout &lt;&lt; *it &lt;&lt; '\n';
    }
}


Or, using the range-for notation of modern C++:

void print(std::vector&lt;int&gt; const&amp; array) {
    for (int e: array) { std::cout &lt;&lt; e &lt;&lt; '\n'; }
}


Who said C++ could not be nifty?