[解決済み] 項目を挿入した後にリストをソートするのと、ソートされたリストに項目を追加するのでは、どちらが速いか？

質問

ソートされたリスト（ソートするためにクイックソートを言う）がある場合、追加する値がたくさんある場合、ソートを中断し、それらを最後に追加し、その後ソートするか、バイナリチョップを使用してアイテムを追加しながら正しく配置する方がよいのでしょうか? 項目がランダムであるか、すでに多かれ少なかれ順序があるかに違いはあるのでしょうか？

どのように解決するのですか?

効果的にゼロからリストを構築するのに十分なアイテムを追加した場合、後でリストをソートすることによってより良いパフォーマンスを得ることができるはずです。

項目がほとんど順番に並んでいる場合、それを利用するために増分更新と通常のソートの両方を微調整することができますが、率直に言って、通常、トラブルに見合うものではありません。 (また、予期しない順序がアルゴリズムに多くの時間を取らせることがないようにするなど、注意する必要があります。 より長い にも注意する必要があります)。

インクリメンタルアップデートと通常のリストソートの両方はO(N log N)ですが、後ですべてをソートすることでより良い定数ファクターを得ることができます（ここでは、インクリメンタルアップデートがO(N)より速くリストアイテムをアクセスできるように、いくつかの補助的なデータ構造を持っていると仮定します...)。 一般に、インクリメンタル アップデートは常に完全な順序を維持しなければなりませんが、一度にまとめてソートすることはそうではないため、一度にまとめてソートすることは、順序をインクリメンタルに維持するよりもはるかに多くの設計上の自由度を持ちます。

もし何もなければ、高度に最適化されたバルクソートがたくさんあることを思い出してください。