この質問はこれまでに何百万回も出されていることは承知していますが、これが少し異なり、もう少し興味深いものになることを願っています。Dor と Zwick の論文に出くわしました。これは、<= 3n の比較で n 個の整数の配列の中央値を見つけることができるというものです。論文はこちら: http://eccc.hpi-web.de/report/1995/031/download
誰かが実際にこれを実装したことがありますか? これは非常に複雑に思えます。実行して、より標準的なバージョンのアルゴリズムと比較するのを楽しみにしています。