Algorithms1.はじめにこのチュートリアルでは、マージソートアルゴリズムとそのJavaでの実装について見ていきます。マージソートは最も効率的なソート手法の1つであり、「分割統治」パラダイムに基づいています。2.アルゴリズムマージソートは、最初に問題を部分問題に分割する「分割統治」アルゴリズムです。これは、主な問題ではなく部分問題を扱うときに再帰を使って簡単に実装できるアルゴリズムの1つです。このアルゴリズムは、次の2段階のプロセスとして記述できます。Divide:このステップでは、入力配列を2つの半分に分割します。ピボットは配列の中点です。このステップは、分割するハーフアレイがなくなるまで、すべてのハーフアレイに対して再帰的に実行されます。ソートしてマージします下から上に並べ替え、ソートされた配列を取得します。{10、6、8、5、7、3、4}の例に対する完全なマージソートプロセスを示しています。ダイアグラムをよく見ると、サイズが1になるまで配列が2つの半分に再帰的に分割されていることがわかります。サイズが1になると、マージプロセスが実行され、ソート中に配列のマージを再開します。これは再帰関数なので、基底条件と再帰条件が必要です。基本条件は、配列の長さが1であるかどうかを確認し、それが返されるだけです。それ以外の場合は、再帰呼び出しが実行されます。関数が両方のサブ配列に対して再帰的に呼び出されます。関数は両方の部分配列の要素を一つずつ比較し、小さい方の要素を入力配列に入れます。一方の部分配列の終わりに達すると、もう一方の配列の残りの要素が入力配列にコピーされ、最終的なソート済み配列が得られます。actual);}4.複雑さマージソートは再帰的アルゴリズムであるため、時間の複雑さは次の再帰的関係として表すことができます。アレイ全体をマージするのに必要な時間です。時間の複雑さは__O(nLogn)になります。場合に当てはまります。5.まとめこのクイックチュートリアルでは、マージソートアルゴリズムの動作と、それをJavaで実装する方法について説明しました。ワーキングコード全体はhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubで利用可能]です。