Optimizing insertion sort for small amounts of data

Question

I'm building a hybrid sort, and for that I need a fast and adaptive sort ideal for small sizes (< 65 elements).

Insertion sort immediately comes to mind, and I've been tinkering with different implementations of it. My requirement is that it takes in iterators as per C++ standard.

Linear insertion sort

template <typename Iter>
void lin_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        auto key = *cur;
        auto ins = cur - 1;
        for (; begin <= ins && key < *ins; --ins)
            *(ins + 1) = *ins;    // move 1 to right until correct position's found
        *(ins + 1) = key;
    }
}

Binary insertion sort

template <typename Iter>
void ins_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        // upper_bound is binary search for correct insertion position
        // shift everything from up to cur to the right one and insert key into right place
        std::rotate(std::upper_bound(begin, cur, *cur), cur, cur + 1);
    }
}

Alternative and equivalent binary insertion sort

template <typename Iter>
void ins_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        auto key = *cur;
        auto ins = std::upper_bound(begin, cur, key);
        for (auto shift = cur; shift != ins; --shift) *shift = *(shift-1); 
        *ins = key;
    }
}

Some benchmarking reveals the binary version to be around 1.5 times slower than the linear version, compiling on GCC 4.8.2 with -O3

mylibs\algo>algotest s l
after: 100000 lists with 64 elements: 1.11421e+06 us    1114.21 ms  (linear insertion sort)
mylibs\algo>algotest s i
after: 100000 lists with 64 elements: 1.62741e+06 us    1627.41 ms  (binary insertion sort)

I am only concerned about its performance for under 65 elements, so the asymptotic guarantee given by binary search is irrelevant. Can anyone suggest improvements to the linear insertion sort, or a better alternative for what I'm looking for?

Benchmarking code: (full testing can be found in algotest)
Generating random data

// random number generation
class Rand_int {
public:
    Rand_int(int low, int high) : distribution{low, high} {
    }
    int operator()() {
        return distribution(engine);
    }

private:
    default_random_engine engine;
    uniform_int_distribution<> distribution;
};

vector<int> randgen(int max, int num) {
    static Rand_int die{0, max};
    vector<int> res;
    res.reserve(num);
    for (int i = 0; i < num; ++i)
        res.push_back(die());
    return res;
}

template <typename T>
vector<vector<T>> data_gen(const string& fname, int l_num = list_num, int l_size = list_size, int r = range) {
    ofstream f {fname};
    f << l_num << ' ' << l_size << ' ' << r << endl;
    vector<vector<T>> v_list;
    v_list.reserve(l_num);
    for (int i = 0; i < l_num; ++i) v_list.push_back(randgen(r, l_size));
    for (auto v : v_list) print(v, f);
    return v_list;
}

template <typename Container>
void print(const Container& v, ostream& os = cout) {
    for (auto x : v)
        os << x << ' ';
    os << '\n';
}

Timing

class Timer {
    time_point<system_clock> init, end;
    microseconds elapsed = duration_cast<microseconds>(end - init);
public:
    Timer() : init{system_clock::now()} {}
    void start() { init = system_clock::now(); }
    double tonow() { 
        end = system_clock::now();
        elapsed = duration_cast<microseconds>(end - init);
        return elapsed.count();
    }
};

//... inside switch case of algotest main
    load_data(v_list);  // v_list is loaded from file
    switch (argv[2][0]) {
        // ... more sorts
        case 'i': for(auto& v : v_list) ins_sort(v.begin(), v.end()); break;
        case 'l': for(auto& v : v_list) lin_sort(v.begin(), v.end()); break;     
        default: cout << "incorrect sort selection\n"; listalgos();
    }

Answer 1

Unfortunately, you are unlikely to find a better sort than the linear insertion sort when it comes to sorting small data sets. The only sorting algorithms that might be faster are sorting algorithms specialized for a given size of input: for example, optimized sorting networks can be really fast if you need to sort a small amount of integers, but are generally slower than the insertion sort if not implemented properly or if used with other types. The following image is a graph that shows the performance of different kinds of sorting algorithms to sort small fixed-size integer arrays (the time in ms corresponds to the time needed to sort one million arrays of a given size). Distributions had a random pattern:

Some of the algorithms were specialized for fixed-size collection; most notably low_comparisons_sorter, low_moves_sorter and sorting_network_sorters. The linear insertion sort was the fastest sorting algorithm which worked for collections of any size; my best bet is that a small collection fits in the fastest cache and thus benefits from the linear access.

Now, the linear version of the insertion sort I use is slightly different: it has a check to make sure that no temporary value is created if the current element is already in place. In your algorithm, it would look like that:

template <typename Iter>
void lin_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        auto ins = cur - 1;
        if (*cur < *ins) {
            auto key = *cur;
            do {
                *(ins + 1) = *ins;  // move 1 to right until correct position's found
                --ins;
            } while (begin <= ins && key < *ins);
            *(ins + 1) = key;
        }
    }
}

I doubt it would change a thing, but you could also try to find the point where to insert the value in a linear fashion, then rotate the values. It may be simpler for a compiler to vectorize code that linearly compares things then linearly copies things rather than a code that mixes comparison and copy operations on-the-fly. I did not test that, so don't take it for granted.

To sum up: for small collection, it's unlikely that you will beat linear insertion sort unless you have specializations for some specific types or some specific sizes, which means more code.