質問: &( (*p)->next ); } ``` のif文が、未ソートの場合は実行される時とされない時があり、ソート済の場合は毎回実行される、ということだと思います。 ですから、むしろソート済のほうが実行時間が長くなるはずだと思うのですが・・・ なぜ未ソートのほうが時間がかかるのか、教えてください。
回答: コンパイラ・CPUの仕様によりますが アセンブリ言語レベルですと CPUの高速化(パイプライン)の都合で条件分岐の予測をCPUが間違えると遅くなります。 ループ内の条件分岐ですので、CPUが**前回の分岐と同方向**を予測するアルゴリズム もしくは、**常に分岐する**と予測するアルゴリズムであった場合 ソート済みか否かで速度が変わる要因になります。 なんとなくですが、三項演算子を用いる事で`cmov`命令に最適化されそうな気がします。 ``` max = comp(*max, *p) < 0 ? p : max; ```