私は、Javaでマージソートのいくつかの実装を見てきました。分割部分は、2つの新しい配列を作成し、左と右を作成し、左と右の部分をそれらの配列にそれぞれコピーすることによって行われるようです。Javaでマージソートし、配列をコピーしても、まだnlogn？
私の質問です：これはまだ私たちにnlognの時間を与えるのですか？今度は各分割にn + n時間（配列を分割するのにn時間、配列をマージするのにn時間）があり、ログ分割があるので、2nlognはまだnlognです。これは正しいです？
あなたはどの実装を見ていましたか？ JDKで使用される主な並べ替えアルゴリズムは、TimSortとComparableTimSort（Object配列/コレクションの場合）DualPivotQuicksort（プリミティブ配列の場合）、および並行ソートの場合はArraysParallelSortHelpersという理解できないウィザードです。
これらのクラスはすべて、QuickSortまたはMergeSortの高度に調整された実装を提供します（または並行処理に適したMergeSortのような音である"CilkSort"）。これらのアルゴリズムはすべて一般的にO（n log（n））です - 入力に追加の制約なしでimpossible to do better than O(n log(n))です。
これらのアルゴリズムが一般にO（n）時間を一時的な記憶域間で前後にコピーするのに費やすかどうかに関しては、大文字小文字の問題です。可能であれば、これらの実装はO（n）の余分なメモリと線形コピーを行う時間の使用を避けようとしますが、実際にはボトルネックではないことがよくあります。たとえば、CilkSortはセカンダリ「ワークスペースアレイ」を使用して連続するステージから前後に値をコピーします。これにより、「前の」ステージは常に信頼できる状態にあるため、インバリアントを適用しやすくなります。それでも、実装は可能な限り不要な配列コピーを避けるようにします。
公開APIレベルでは、Collections.sort()は.toArray()を呼び出し、配列をソートしてから、元のListに値をコピーします。同じように実際に最適化されています。Listをインプレースに変更するすべてのメソッド呼び出し（および場合によっては非効率なListの実装など）を処理するよりも、配列をソートして2つの線形コピーを実行する方が高速です。
はい。 O（2n logn）はまだO（n logn）です。 – Thilo
さらに、配列分割がインプレースで行われます。新しい配列そのものではありません。 –
私はインプレース配列ディビジョンを実装しようとしていますが、それはちょっと混乱しているようです。元の配列の開始と終了のインデックスを正しく追跡する必要がありますか？実装するのは難しいようではありませんが、新しい左と右の配列を作成するよりもエラーの箇所が多いようです。 – Kevin