void inplace_merge(int* start, int* middle, int* end)
{
int *mt = middle;
while ( start < middle )
{
if ( *start > *middle )
{
int v = *start;
mt = middle + 1;
swap( *start, *middle );
while ( mt < end && v > *mt )
{
mt[-1] = *mt;
mt++;
}
mt[-1] = v;
}
start++;
}
}

или используйте STL.