Slow merge sort

template
void merge_sort(Iterator start, Iterator fin, int sort_type) {

    Compare comp;

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

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

        merge_sort(left.begin(), left.end(), 2);
        merge_sort(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
void merge_sort(Iterator start, Iterator fin, int sort_type) {

Compare comp;

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

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

merge_sort(i, j, 2);
merge_sort(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){

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.

StackExchange Code Review Q#118237, answer score: 2