Slow merge sort

Question

template<class Compare, class Iterator>
void merge_sort(Iterator start, Iterator fin, int sort_type) {

    Compare comp;

    typedef typename iterator_traits<Iterator>::value_type _value_type;  //black type magic to infer data type

    if (distance(start, fin) > 1) {
        vector<_value_type> left (start, start+distance(start, fin)/2);
        vector<_value_type> right (start+distance(start, fin)/2, fin);

        merge_sort<Compare>(left.begin(), left.end(), 2);
        merge_sort<Compare>(right.begin(), right.end(), 2);

        auto i = left.begin();
        auto j = right.begin();

        while (i!= left.end() or j!= right.end()) {
            if (i == left.end()) {
                *start++ = *j++;
            } else if (j == right.end()) {
                *start++ = *i++;
            } else if (comp(*i, *j)) {
                *start++ = *i++;
            } else {
                *start++ = *j++;
            }
        }
    }

So, I've written this implementation of merge_sort, but it seems to be quite slow --- it took 1500ms to sort a vector of 1 000 000 random ints, while standard qsort did the same in less than a tenth of that --- 130ms. Is there (and there definitely is) something wrong with my code, and how can I fix it so that it's more effective?

UPDATE: So, umm, I've updated the code and is should use only one auxiliary vector. The speed did not improve much, though. Anything else?

template<class Compare, class Iterator>
void merge_sort(Iterator start, Iterator fin, int sort_type) {

    Compare comp;

    typedef typename iterator_traits<Iterator>::value_type _value_type;  //black type magic to infer data type
    if (distance(start, fin) > 1) {
        static vector<_value_type> temp (distance(start, fin), 0);

        auto i = start;
        auto j = start + distance(start, fin)/2;
        auto k = temp.begin();

        merge_sort<Compare>(i, j, 2);
        merge_sort<Compare>(j, fin, 2);

        while (i != start+distance(start, fin)/2 or j != fin) {
            if (i == start+distance(start, fin)/2) {
                *(k++) = *(j++);
            } else if (j == fin){
                *(k++) = *(i++);
            } else if (comp(*i, *j)) {
                *(k++) = *(i++);
            } else {
                *(k++) = *(j++);
            }
        }

        copy(temp.begin(), temp.begin()+distance(start, fin), start);

    }

UPDATE 1.5 It's a miracle this even works; it definitely shouldn't. I'll fix this later.

Answer 1

Don't allocate a vector in each recursive call

You just need one copy of the whole vector as a parameter, then use both as the auxiliary interchangeably at each recursive call.

Example in Java so you can see what I mean (Taken from this source here ):

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
   if (hi <= lo) return;
   int mid = lo + (hi - lo) / 2;
   sort (aux, a,lo, mid);
   sort (aux, a, mid+1, hi);
   merge(a, aux, lo, mid, hi);
}

Use insertion sort as base case

You can use insertion sort as a base case for a given threshold (Use some benchmarks to find it. Insertion sort is faster for smaller inputs.

Answer 2

In a merge sort (and quick sort) you need to stop your recursion when there is a handful of iterations left (say 32 elements) and then use an in-place sort (some even use bubblesort shrugs) to sort the last elements in that range. The reason is that the recursion and splitting overhead becomes too large when the number of elements are small.