Algorithm

1. Start by considering the first element of the array as the sorted subarray.

2. Take the next element and compare it with each element in the sorted subarray from right to left (towards index zero).

3. If the current element is smaller than the element being compared, then shift the element being compared one position to the right.

4. Repeat this until you find the correct position to insert the current element.

5. Insert the current element in the correct position and continue the process with the next element until the entire array is sorted.

Implementation

Follow the steps in the algorithm above, and use the comments for reference. Spend some time following each step carefully and you will understand it.

void insertion_sort(std::vector<int> &v)
{
/* 1. Element at index [0] is sorted, start from index [1] */
    for (int a = 1; a < v.size(); ++a)
    {
        int b;
/* 2. Compare the stored element with the sorted array */
        int tmp = std::move(v[a]);
        for (b = a; b > 0 && tmp < v[b - 1]; --b)
        {
/* 3/4. Shift all elements smaller than the stored element */
            v[b] = std::move(v[b - 1]);
        }
/* 5. Insert the stored element at the correct position */
        v[b] = std::move(tmp);
    }
}

Time Complexity

The overall time complexity of the function is squared as shown below, where n is the size of the input array.

$$\frac{n\times (n-1)}{2} \approx O(n^2)$$

The best-case scenario is a sorted array, giving a case-based linear time complexity.

Best case:

Input => [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

Output => [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

The worst-case scenario is a reverse sorted array, giving a case-based squared time complexity.

Worst case:

Input => [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]

Output => [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

To increase the readability of the output I've added some print-to-terminal functionality. The best-case scenario never runs through the inner loop, while the worst-case scenario ends up running through the inner loop n times at the last run.

user@computer:~$ g++ -o a sorting_algos.cpp 
user@computer:~$ ./a
|Test insertion sort best case|
==============1==============
==============2==============
==============3==============
==============4==============
==============5==============
==============6==============
==============7==============
==============8==============
==============9==============
|Test insertion sort worst case|
==============1==============
9,
==============2==============
8, 9,
8,
==============3==============
7, 8, 9,
7, 8,
7,
==============4==============
6, 7, 8, 9,
6, 7, 8,
6, 7,
6,
==============5==============
5, 6, 7, 8, 9,
5, 6, 7, 8,
5, 6, 7,
5, 6,
5,
==============6==============
4, 5, 6, 7, 8, 9,
4, 5, 6, 7, 8,
4, 5, 6, 7,
4, 5, 6,
4, 5,
4,
==============7==============
3, 4, 5, 6, 7, 8, 9,
3, 4, 5, 6, 7, 8,
3, 4, 5, 6, 7,
3, 4, 5, 6,
3, 4, 5,
3, 4,
3,
==============8==============
2, 3, 4, 5, 6, 7, 8, 9,
2, 3, 4, 5, 6, 7, 8,
2, 3, 4, 5, 6, 7,
2, 3, 4, 5, 6,
2, 3, 4, 5,
2, 3, 4,
2, 3,
2,
==============9==============
1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 2, 3, 4, 5, 6, 7, 8,
1, 2, 3, 4, 5, 6, 7,
1, 2, 3, 4, 5, 6,
1, 2, 3, 4, 5,
1, 2, 3, 4,
1, 2, 3,
1, 2,
1,