再帰深度を抑えた要素の追加
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