0

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.