Merge Sort.

mergesort( int a[], unsigned int n )
{
int *tmp_array;
tmp_array = (int*) malloc ( (n+1) * sizeof (int) );
if( tmp_array != NULL )
{
m_sort( a, tmp_array, 1, n );
free( tmp_array );
}
else
printf("No space for tmp array!!!");
}
void m_sort( int a[], int tmp_array[ ],int left, int right )
{
int center;
if( left < right )
{
center = (left + right) / 2;
m_sort( a, tmp_array, left, center );
m_sort( a, tmp_array, center+1, right );
merge( a, tmp_array, left, center+1, right );
}
}

void merge( int a[ ], int tmp_array[ ],int lpos,int rpos,int rend)
{
int i, lend, n, tmp_pos;
lend = rpos - 1;
tmp_pos = lpos
n = rend - lpos + 1;
/* main loop */
while( ( lpos <= lend ) && ( rpos <= rend ) )
if( a[lpos] <= a[rpos] )
tmp_array[tmp_pos++] = a[lpos++];
else
tmp_array[tmp_pos++] = a[rpos++];
while( lpos <= lend )  /* copy rest of first half */
tmp_array[tmp_pos++] = a[lpos++];
while( rpos <= rend ) /* copy rest of second half */
tmp_array[tmp_pos++] = a[rpos++];
/* copy tmp_array back */
for(i=1; i <= n; i++, rend-- )
a[rend] = tmp_array[rend];
}