in-place merge sort - 鍋あり谷ありhttp://blog.livedoor.jp/dankogai/archives/50957658.html に 現代では一時メモリーを使わないin-place merge sortが開発されている と書いてある。そういえば、STLの stable_sort の計算量が O( N (log N)**2 )だったよなぁと思い、どうやったらそうなるのか調べてみたら http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html に実装があるのを発見した（いやその前にSTLのソースを見たんだが、とても読みにくかったので断念した）。 で。ソースから計算内容を理解し、ああなるほどそうするのかと思ってみた。 というわけで、どんな計算なのかを私なりに説明してみる： 左半分と右半分を整列する。 左半分と右半分をマージする。 こ
