On problem with mergesort is that it constantly needs a new temporary array. One solution to the problem is to rewrite the mergesort according to the following specification:

void mergesort( int data[ ], int first, int n, int temp[ ] ); // Precondition: data[first] through // data[first+n-1] are array elements in no // particular order. The temp array has // locations temp[first] through // temp[first+n-1]. // Postcondition: The elements // datalfirst] through data[first+n-1] // have been rearranged so that they are // ordered from smallest to largest. The array // elements temp[first] through // temp[first+n-1] have been used as // temporary storage.