MergeSort performance Do you see any inefficient parts with the following code? On internet I see 30 ms for 100.000 integers but I can sort 100.000 integers in 300ms. The data is random. I am using late 2013 macbook pro so I don't expect a 10x slowdown from CPU, but who knows.

void mergesort2(int* list, int begin, int end,int *tmplist=0){
    bool allocated = false;
    if (end-begin &lt; 1) {
        return;
    }
    if (tmplist == 0) {
        allocated = true;
        tmplist = new int[end-begin+1];
    }

    int middle = (begin+end)/2;

    mergesort2(list, begin, middle, tmplist);
    mergesort2(list, middle+1, end, tmplist);

    for (int first=begin, second=middle+1, tmp=0; tmp&lt;end-begin+1; tmp++) {
        if (first &gt; middle) {

            memcpy(tmplist+tmp, list+second, sizeof(int)*(end-begin-tmp+1));
        }
        else if (second &gt; end) {
            memcpy(tmplist+tmp, list+first, sizeof(int)*(end-begin-tmp+1));

        }
        else if (list[first] &lt;= list[second]) {
            tmplist[tmp] = list[first++];
        }else{
            tmplist[tmp] = list[second++];
        }
    }

    memcpy(list+begin, tmplist, (end-begin+1)*sizeof(int));

    if (allocated) {
        delete tmplist;
    }
}
A C++ merge sort in the style of a Standard Library algorithm could be written as 

template&lt;class BiDirIt, class Compare = std::less&lt;typename std::iterator_traits&lt;BiDirIt&gt;::value_type&gt;&gt;
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare())
{
        auto const N = std::distance(first, last);
        if (N &lt; 2) return;
        auto middle = std::next(first, N / 2);
        merge_sort(first, middle, cmp);
        merge_sort(middle, last, cmp);
        std::inplace_merge(first, middle, last, cmp);
}


Let's look at how this improves upon your design:


generic interface: it takes two iterators and a comparison function of arbitrary types, instead of two indices into a pointer to an array of int and the implicit but fixed &lt; comparison.
in-place: behind the covers it calls std::inplace_merge that can allocate extra memory but it does it so that users don't have to supply this, instead of your tmplist parameter.
half-open intervals: it will split the input range [first, last) into [first, middle) and [middle, last) which automically takes care of easy to make "off-by-one" errors in code like middle + 1 (in your code it is correct, but you still have to think about it, half-open intervals are easier to get right).
named algorithms: it uses std::inplace_merge as a ready-to-use component instead of a somewhat long and certainly tricky final step in your algorithm. Not only makes this your merge_sort more compact, the inplace_merge itself is a resuable component in its own right!
heavily optimized: Standard Library experts are very likely to know about the state of the art in writing performance-optimized algorithms. A factor of 10 of performance compared to your code seems a lot, but if you forget some hidden copies, use a hand-written loop that has O(N^2) complexity instead of O(N log N) you can quickly get there.