After fixing the problem @RichHendricks pointed out this still has...not a problem exactly, but still a design that's less than optimal (at least in my opinion).
In the initial phase, you basically do:
calculate middle
recurse on left side
recurse on right side
Each of those recursive calls does the same thing again. Modern processors have done quite a bit to make calls and returns more efficient, but that still adds quite a bit of overhead when the fundamental operation involved is basically just computing the arithmetic mean of two numbers.
You can avoid that by using a bottom-up merge-sort. Instead of recursively splitting the array in half until it gets down to some manageable size, you can simply take the first N elements and sort them with some low-overhead sort (typically an insertion sort). Repeat N elements at a time until you reach the end of the collection (though, of course, the last group might not be the same same size as the others).
Then take the first two sorted groups of N elements and merge them. Repeat for the next pair of groups until you reach the end. Repeat that process until all the groups have been merged into one.
As to how to do the merging: a couple of papers1 have been written about in-place merging. I should add that quite a few algorithms to do this have been devised, but many (most?) are primarily theoretical--in theory, they have low enough computational complexity to maintain the O(N log n) complexity of the merge sort as a whole, but in fact they impose so much overhead that other methods are faster for almost any practical amount of data. I've tried to restrict the list of citations below to ones that seem to have at least some chance of being practical, not just theoretical.
One last point: contrary to one widespread belief, this is an area where you actually stand a pretty decent chance of writing code significantly better than the standard library provides. The C++ standard library does include an inplace_merge algorithm, but it's allowed to be significantly slower than the best algorithms now known. At least if I recall correctly these requirements haven't been updated since the 1998 standard, which was before many of the best in-place merging algorithms were invented. I don't claim to have looked at every implementation of in-place merging in every standard library, but I have seen at least a few relatively recent ones that used older, substantially less efficient algorithms.
- For a few examples:
http://akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/Huang88.pdf
http://www.sofsem.cz/sofsem06/data/prezentace/23/A/Kim-OnOptimalandEfficientInPlaceMerging.ppt
http://www.dcs.kcl.ac.uk/technical-reports/papers/TR-04-05.pdf
operator new[]
but delete withoperator delete
. You should clean uptmplist
withdelete [] tmplist;
\$\endgroup\$