Optimizing insertion sort for small amounts of data I'm building a hybrid sort, and for that I need a fast and adaptive sort ideal for small sizes (&lt; 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 &lt;typename Iter&gt;
void lin_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        auto key = *cur;
        auto ins = cur - 1;
        for (; begin &lt;= ins &amp;&amp; key &lt; *ins; --ins)
            *(ins + 1) = *ins;    // move 1 to right until correct position's found
        *(ins + 1) = key;
    }
}


Binary insertion sort

template &lt;typename Iter&gt;
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 &lt;typename Iter&gt;
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&gt;algotest s l
after: 100000 lists with 64 elements: 1.11421e+06 us    1114.21 ms  (linear insertion sort)
mylibs\algo&gt;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&lt;&gt; distribution;
};

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

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

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


Timing

class Timer {
    time_point&lt;system_clock&gt; init, end;
    microseconds elapsed = duration_cast&lt;microseconds&gt;(end - init);
public:
    Timer() : init{system_clock::now()} {}
    void start() { init = system_clock::now(); }
    double tonow() { 
        end = system_clock::now();
        elapsed = duration_cast&lt;microseconds&gt;(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&amp; v : v_list) ins_sort(v.begin(), v.end()); break;
        case 'l': for(auto&amp; v : v_list) lin_sort(v.begin(), v.end()); break;     
        default: cout &lt;&lt; "incorrect sort selection\n"; listalgos();
    }
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 &lt;typename Iter&gt;
void lin_sort(Iter begin, Iter end) {
    for (auto cur = begin; cur != end; ++cur) {
        auto ins = cur - 1;
        if (*cur &lt; *ins) {
            auto key = *cur;
            do {
                *(ins + 1) = *ins;  // move 1 to right until correct position's found
                --ins;
            } while (begin &lt;= ins &amp;&amp; key &lt; *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.