understanding this mergesort algorithm?

Question

I have the following code

void mergesort(int size, int ar[], int temp[])
{
    if(size <=1)
    {
        return;}
    else
    {
        int i = 0;
        int mid = size/2;

        int *left = &ar[0];
        int *right = &ar[mid];
        int *rend = &ar[size];
        int *lend = right;

        mergesort(mid,left,temp);
        mergesort(size-mid,right,temp);

        for(i=0; i<size;i++)
        {
            if(left < lend && (*left < *right || right >= rend))
            {
                temp[i] = *left++;
            }
            else
            {
                temp[i] = *right++;
            }
        }
        for(i = 0; i < size; i++)
        {
            ar[i] = temp[i];
        }
    }
}

I couldn't understand how this if statement works:

if(left < lend && (*left < *right || right >= rend))
{
   temp[i] = *left++;
}
else
{
   temp[i] = *right++;
}

Can you tell me what's going on in there? Why do we have to compare addresses? (left < lend and right >= rend)

Here's how the mergesort function is called from main

const int SIZE = 8;
int array[SIZE] = {3,6,1,-9,0,2,4,5};
int temp[SIZE];

mergesort(SIZE, array,temp);

Answer 1

In order to choose the input between the left or right sequences, you need to know if the sequence is exhausted. You check this by testing the pointer to see if it's beyond the valid range. left < lend returns true if the left sequence is not exhausted, and right >= rend returns true if the right sequence is exhausted. Thus the if will be taken when the left sequence isn't exhausted, and either the left item is less than the right item or the right sequence is exhausted.

If you were following the standard library iterator conventions, you would never check for < or > in a comparison. left != lend and right == rend would work just as well in the code you posted.

P.S. two thoughts that aren't part of your question:

1. As noted in the comments, there's undefined behavior lurking in the comparison. You need to test if the right side is exhausted before checking the value at the right side pointer.
2. Merge sort is naturally stable if you use the correct comparison. You want any ties to take from the left sequence. In your case of sorting ints it doesn't matter since you can't tell one identical int from another, but if this was just a key in part of a larger structure it could matter greatly. It's just a matter of replacing < with <=.

Taking all the above suggestions together you end up with:

if (left != lend && (right == rend || *left <= *right))

Answer 2

Hariprasad is right. Then you make a comparison left < lend, you compare the addresses of some elements. Because array is a concequtive set of addresses, the pointers can be used like the indexes and iterators. And then you make the comparison *left < *right, for example, you compare the values, of course, and determine the less of them.

Answer 3

There are multiple problems with this code:

1. int *rend = &ar[size]; -- Reads beyond the end of the array ar
2. (*left < *right || right >= rend) -- I believe this should be (right > (rend - 1) || (*left > *right)) in order to avoid reading beyond the end of ar.

You can work it out for yourself by stepping through the code with an initial array size of 2 or 3. Either exposes the problems quickly. I did this quickly in my head but did not test with a debugger. Caveat Emptor.