From what I can see from Robert Sedgewick's Algorithms in C, a mergesort algorithm becomes significantly more complex - possibly affecting the stability of the sort, something which is a valued property of a mergesort - when it is modified to do an in-place sort, removing the requirement of extra space proportional to the number of records.

If the the extra space is a problem, something like a heapsort may be an alternative.
Both mergesort and heapsort algorithms generally have N log N runtimes.

Cheers.

BazB

Update: BTW, I recommend the aforementioned book if you're interested in an easy to understand, but complete, reference to algorithms.
I've not looked at O'Reilly's Mastering Algorithms with Perl , however I believe it is also a great textbook.

I've only used a basic mergesort, so have no personal experience with more complex implementations.