再帰深度を抑えた要素の追加

merge_sortのマージ部分の再帰深度を抑えられないかという話。
手始めにソート済み配列に、再帰深度対数オーダーで1要素追加することを考えた。

http://melpon.org/wandbox/permlink/nIsePEbv8EY3D9Lo

しかし、再帰深度は抑えられたものの、これは考えうる配列のソート順の組み合わせ全列挙してから、正しくソート済みの物を選択してるのと変わらないので計算量が…。

Dt氏の協力を得て再帰深度を抑えたmerge_sortが実現したものの実用性は…。 http://melpon.org/wandbox/permlink/p6u3iCvYMkd3xL7G

再帰深度を抑える努力がこうじてスタックオーバーフローしないものの、再帰だけでconstexpr evaluation hit maximum step limit;するのでほぼ詰み…。

参考 : コンパイルマージソートの話
http://dtyazsk.blog.shinobi.jp/c--/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%AB%E6%99%82%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88%E3%81%AE%E8%A9%B1