4
\$\begingroup\$

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();
    }
\$\endgroup\$
7
  • \$\begingroup\$ What's the sample data you used for benchmarking? Could that have affected the difference in the relative performances of the two sorting methods? \$\endgroup\$
    – R Sahu
    Nov 29, 2014 at 6:16
  • \$\begingroup\$ My sample data is generated with a default_random_engine on a uniform_int_distribution; not sure how random data would benefit one over another \$\endgroup\$
    – LemonPi
    Nov 29, 2014 at 6:49
  • \$\begingroup\$ The benchmarking code is the usual suspect. May we see it? \$\endgroup\$
    – vnp
    Nov 29, 2014 at 6:55
  • \$\begingroup\$ @LemonPi, given your response, I don't see any reason for a bias that would benefit one sorting method over another. \$\endgroup\$
    – R Sahu
    Nov 29, 2014 at 7:11
  • \$\begingroup\$ One thing that appears to be happening, in your benchmarking code, is that, you're including the console output in the timing. This can skew your results since once the screen buffer is full, subsequent writes are much slower. Any console output should be removed from the timing. \$\endgroup\$
    – user33306
    Nov 30, 2014 at 12:34

1 Answer 1

4
\$\begingroup\$

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:

Small array sorts

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.