マージソートってふつーにやると多分対象の配列に対して同一サイズのメモリを別途用意するのがお手軽なんだけど、そういったメモリをなるべく確保せずに(配列サイズNに対してO(1)に近いレベルのメモリ確保で)マージできねーかなーと。いや、出来ないと割と困るんじゃないですかね。
http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
えーと大変分かりづらいんですけど、多分 merge の際に
------****** <- ------ と ****** はそれぞれソートされている
---+--***||| <- | は + の値以上の値を持つ要素。+は適当に選ぶ
---***+--||| <- +-- と *** を入れ替える
とやって、---***と+--|||に対してまた再帰的に merge すればこの部分O(N logN)だよね、と。
多分。ん、ところで授業で習ったとかいうことはあるのか？
