How to sort in-place using the merge sort algorithm?
- by eSKay
I know the question is too open.
All I want is someone to tell me how to convert a normal merge sort into an in-place merge sort (or a merge sort with constant extra space overhead).
All I can find (on the net) is pages saying "it is too complex" or "out of scope of this text". "The only known ways to merge in-place (without any extra space) are too complex to be reduced to practical program." (from here)
Even if it is too complex, can somebody outline the basic concept of how to make the merge sort in-place?