Insertion sort implementation in C++
In both this and your bubble sort implementation you need to start using C++ idioms (otherwise this is just C code (that's fine C is a great language it's just not C++)). 

I would say this is the perfect C implementation of insertion sort.

But usually when you implement these kinds of algorithms in C++ you use iterators to specify the range (as this allows you to sort several types of container including arrays).

Rather than:

void insertionSort(int a[], int s) {


You should probably use:

template&lt;typename I&gt;
void insertionSort(I begin, I end) {


Then you can sort any type of container with:

int  a[] = {1,4,5,27,3,9,1};
insertionSort(std::begin(a), std::end(a));

std::vector&lt;int&gt; v = {1,4,5,27,3,9,1};
insertionSort(std::begin(v), std::end(v));

etc...


Interestingly this also allows you to sort any type (not just integers). As long as your type supports the comparison operator. The standard library tends to implement any comparison in terms of operator&lt;() so to avoid confusion with potential users you should implement your sort using the less than operator and potentially allow the user to specify the actual comparison operator.

// Unless you have an explicit override.
// std::less&lt;T&gt; uses `operator&lt;()` to do the comparison.
// So this means the algorithm will work for type T under three situations.
//    1) operator&lt; is defined for the type T
//    2) There is an specialization of `std::less&lt;&gt;` for type T
//    3) An explicit type is provided to the sort for comparing type T.
template&lt;typename I, typename Comp = std::less&lt;T&gt;&gt;
void insertionSort(I begin, I end) {
    Comp   comp;
    // Stuff