1 of 3
EralpB
  • 173
  • 4

Why is the performance of my mergesort poor?

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 < 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<end-begin+1; tmp++) {
    if (first > middle) {
        
        memcpy(tmplist+tmp, list+second, sizeof(int)*(end-begin-tmp+1));
    }
    else if (second > end) {
        memcpy(tmplist+tmp, list+first, sizeof(int)*(end-begin-tmp+1));
     
    }
    else if (list[first] <= list[second]) {
        tmplist[tmp] = list[first++];
    }else{
        tmplist[tmp] = list[second++];
    }
}

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

if (allocated) {
    delete tmplist;
}
}
EralpB
  • 173
  • 4