Sorting Efficiency Question

[c++noobie]

I recently learned a little bit about sorting algorithm efficiency. I looked at the merge sort and saw how it could be implemented using a scratch array to store the result until it was finished. It then talked about in place algorithms but didn't offer one for a merge sort, so I tried to build my own. I came up with one:

/* this assumes sub1 and sub2 are start points of two sub arrays of one contiguous array starting at sub1 with size elements */
int* merge ( int *sub1, int *sub2, int size )
{
    int *final= sub1, count= 0;

    while ( ++count < size )
    {
        if ( *sub1 > *sub2 )
        {
            /* if arr2 is less, move it to next slot in final */
            int *loc= sub2++;
            while ( loc-- > arr1 )
            {
                loc[0]^= loc[1];
                loc[1]^= loc[0];
                loc[0]^= loc[1];
            }
        }
        /* move the first pointer */
        arr1++;
    }

    return final;
}

int* merge_sort ( int *arr, int size )
{
    if ( size == 1 )
        return arr;
    else
        return merge( merge_sort( arr, size/2 ),
                      merge_sort( arr+size/2, size/2+size%2 ),
                      size );
}

I was wondering if this defeats the program efficiency in order to obtain the in place functionality when it has to iterate in the sort function to move a lesser value up in the final. How would this affect the runtime? Thanks in advance for anything anyone may offer.

[Aia]

Merge Sort Algorithm Analysis

[c++noobie]

Thank you, but I had seen something similar to that in what I was reading. What I read was talking about in place algorithms (ones that don't consume extra memory, e.g. no second array for merge sort) though and I was wondering if my in place solution provided above sacrificed it's execution speed by becoming in place like it is. Perhaps I should clarify what I was asking:

1) Does the in place solution provided above lose it's execution speed by saving memory like it does? (specifically lines 8 to 18 when it iterates down the array to move a value)

2) Is it even still a merge sort after the modifications I made? (maybe it's still a logical merge sort but no longer a physical merge sort?)

If I need to clarify anything in the code or anything else please ask, and thanks to anyone who may have an answer.

[c++noobie]

I'm sorry I quickly brushed over the example on my way out the door. Thank you for your response. Now that I have time to go back and look at it, it is a little more helpful. One more question I would like to know though, would my code provided even be a merge sort at this point or is it something else?

[ArkM]

It's wonderful but just before talking about this code run-time speed and other characteristics correct obvious errors in it. Now you can't compile this code: arr1 is not declared in the merge function (if it's a global variable better don't display this "improved" sort function)...

When you compile this improved merge sort code you can test and profile it - and you will get all answers to your questions...

PS. As usually, xor based solution is much more expensive than a simple swap...

[c++noobie]

Thanks to both of you for your input. As for the error, it started off as arr1 and arr2 instead of sub1 and sub2 but I changed them to make it more apparent that they are sub arrays of a larger one, not complete separate arrays. As for my question, after looking further into it, it is less efficient to save memory in that case. It winds up having run time similar to a selection or insertion sort. Thanks to both of you.