C++ merge sort not working

Question

I am trying to implement merge sort, but I cannot get it to work. I would be really grateful if anyone could find and point out the error in my thinking (and code).
Main function without unnecessary code:

int main(int argc, char *argv[]) {
    int n = 0;
    std::cin >> n;
    int num[n];

    for(int i = 0; i < n; i++) {
        std::cin >> num[i];
    }

    sort(num, &num[n - 1], n);

    return(0);
}

Merge sort function:

int *sort(int *s, int *e, int size) {
    if(s == e) {
        return(s);
    }

    int mid = (size + 1) / 2;

    //split array recursively to 1-element arrays

    int *left  = sort(s, (s + mid - 1), mid);
    int *right = sort(s + mid, e, size - mid);

    int *counter = s;

    //merge arrays back together

    while(left < (s + mid - 1) && right <= e) {
        //std::cout << *left << " " << *right << std::endl;

        for(; left < (s + mid - 1) && *left <= *right; left++, counter++) {
            *counter = *left;
        }

        for(; right <= e && *right <= *left; right++, counter++) {
            *counter = *right;
        }
    }

    for(; left < (s + mid - 1); left++, counter++) {
        *counter = *left;
    }
    for(; right <= e; right++, counter++) {
        *counter = *right;
    }

    return(s);
}

input0:
5
4 3 2 1 0
output0:
0 0 0 0 0

input1:
5
0 1 2 3 4
output1:
1 2 4 4 4

input2:
2
0 1
output2:
1 1

Answer 1

Your problem seems to be at *counter = *left and *counter = *right.A usual implementation of the algorithm uses a separate array for creating the new merged array. But in this case , you are merging it inplace. When you do *counter = *left that value is lost and this probably leads to all the zeros you see in your sample run.

When you are merging , you could do it in two ways. Either create a temporary array and keep on writing to it instead of the *counter and refill the actual array with the temporary array after you exhaust all the elements of both arrays, or resort to an insertion sort, once the array size to be merged is less than a predefined value .

Both these methods are given in detail in http://en.literateprograms.org/Merge_sort_%28C%29

PS:I also think you should change the condition left < (s + mid - 1) to left <=(s + mid -1) in all the places .

Answer 2

It looks like you are copying one value over another without saving the original value (and doing something with it):

*counter = *left;