Insertion Sort - Handling empty list

Question

I'm trying to implement insertion sort using stl and vectors. I came up with this solution so far:

void insertionSort(vector<int> &v, int splitIndex);

int main() {

    //vector<int> x = {55,33,99,11,22,44};
    //vector<int> x = {55};
    //vector<int> x = {55,11};
    vector<int> x;

    insertionSort(x, 0);

    printVector(x);

    return 0; }

void insertionSort(vector<int> &v, int splitIndex) {

    vector<int>::iterator right = v.begin() + splitIndex + 1;

    if(right == v.end())
        return;

    vector<int>::iterator left = v.begin() + splitIndex;

    while(*right < *left && right != v.begin()) {
        iter_swap(right, left);
        right--;
        left--;
    }

    insertionSort(v, splitIndex+1); }

It's working on all cases except for the empty vector case because the "right" pointer will be pointing outside the vector limit. I know it can be fixed by adding a condition on the beginning:

if(v.size() < 2) return;

But I don't like that tis condition will be executed for every recursion call.

Please advice. Thanks.

Answer 1

In general this statement

vector<int>::iterator right = v.begin() + splitIndex + 1;

can result in undefined behavior particularly when the vector is empty.

This loop

while(*right < *left && right != v.begin()) {
    iter_swap(right, left);
    right--;
    left--;
}

also can have undefined behavior because before comparing the dereferenced iterators *right < *left you should at first be sure that right != v.begin(). Otherwise the iterator left will be outside the valid range of iterators for the vector.

I am suggesting the following function definition

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

void insertionSort( std::vector<int> &v, std::vector<int>::size_type i = 0 )
{
    if ( i < v.size() )
    {
        auto right = std::next( v.begin(), i );
        auto left = right;

        for ( ; right != v.begin() && *right < *--left; --right ) 
        {
            std::iter_swap( right, left );
        }

        insertionSort( v, i + 1 );
    }
}


int main() 
{
    std::vector<int> v0;
    std::vector<int> v1 = { 55 };
    std::vector<int> v2 = { 55, 11 };
    std::vector<int> v3 = { 55, 33, 99, 11, 22, 44 };

    insertionSort( v0 );

    std::cout << "v0:";
    for ( int x : v0 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v1 );

    std::cout << "v1:";
    for ( int x : v1 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v2 );

    std::cout << "v2:";
    for ( int x : v2 ) std::cout << ' ' << x;
    std::cout << std::endl;

    insertionSort( v3 );

    std::cout << "v3:";
    for ( int x : v3 ) std::cout << ' ' << x;
    std::cout << std::endl;

    return 0;
}

The program output is

v0:
v1: 55
v2: 11 55
v3: 11 22 33 44 55 99