Szerintem egy kicsit túlbonyolítod a problémát, de ami szemet szúrt igazán, az ez: az in-place merge sort műveleti igénye az bizony O(n*(log n)^2).
A tárigénye tényleg 1 és stabil, de ennek ez az ára.
Ezt ajánlom mert jól jöhet még:
http://en.wikipedia.org/wiki/Sorting_algorithm