概要
マージソートメソッドは、2つの（または2つ以上）順序付けられたテーブルを新しい秩序化されたテーブルにマージすることです。つまり、シーケンスをいくつかのサブシーケンスに分割します。各サブシーケンスが順序付けられます。次に、順序付けられたサブシーケンスが全体的な順序付けされたシーケンスにマージされます。
マージのソートは、「分割と征服」に属する再帰を使用して実装されます。ターゲット配列は中央から2つに分割され、2つの配列が個別にソートされます。ソートが完了すると、2つの配列が一緒に「マージ」されます。マージソートで最も重要なことは、「マージ」プロセスです。マージプロセスでは、マージする必要がある2つの配列と一致する追加スペースが必要です。
複製画像：
ステップ
そのサイズが2つのソートされたシーケンスの合計であるようにスペースを適用します。このスペースは、マージされたシーケンスを保存して2つのポインターを設定するために使用されます。初期位置は、2つの並べ替えられたシーケンスの開始位置であり、2つのポインターが指す要素を比較し、比較的小さな要素を選択してマージされたスペースに入れ、ポインターを次の位置に移動します。ポインターがシーケンスの端に達するまでステップ3を繰り返します。他のシーケンスの残りの要素をすべてコピーして、マージされたシーケンスの最後に直接コピーします。
生データ：
3 5 2 6 2
マージの前提条件は、配列を分離し、それらを2つに分割してから2つに分割することです。
最初のラウンドは分離され、インデックス2（（0+4）/2 = 2）は中央です
[3 5 2] [6 2]
分離の第2ラウンド、分離[3 5 2]
[3 5] [2] [6 2]
分離の第3ラウンド、分離[3 5]
[3] [5] [2] [6 2]
マージ[3] [5]
[3 5] [2] [6 2]
マージ[3 5] [2]
[2 3 5] [6 2]
第4ラウンドは分離され、分離[6 2]
[2 3 5] [6] [2]
マージ[6] [2]
[2 3 5] [2 6]
マージ[2 3 5] [2 6]
[2 2 3 5 6]
コード実装（Java）
パッケージcom.coder4j.main.arithmetic.sorting; public class merge {private static int mark = 0; / ** * MERGE SORT * * @PARAM ARRAY * @PARAM LOW * @Param High * @return * / private static int [] sort（] array、int low、int high）{int mid =（low + high） / 2; if（low <high）{mark ++; System.out.println（ "Throwth in Progress" + Mark + "後続の分離、GET"）; System.out.println（ "[" + low + " - " + mid + "] [" +（mid + 1） + " - " + high + "]"）; //左配列のソート（配列、低、MID）; //右配列ソート（配列、中間 + 1、高）; //左右のマージ（配列、低、中、高）; } return array; } / ** *アレイのマージ * * @param array * @param low * @param mid * @param high * / private static void merge（int [] array、int low、int mid、int high）{system.out.println（ "merge：[" + low + " - " + mid + "]および[" int [] temp = new int [high -low + 1]; int i = low; //左ポインターint j = mid + 1; //右ポインターint k = 0; //最初に小さな数値を新しい配列に移動します（i <= mid && j <= high）{if（array [i] <array [j]）{temp [k ++] = array [i ++]; } else {temp [k ++] = array [j ++]; }} // 2つの配列のいずれかに残りの要素がある場合があります//左側の残りの数値を配列に移動します（i <= mid）{temp [k ++] = array [i ++]; } //右の残りの数値を配列に移動しますが、（j <= high）{temp [k ++] = array [j ++]; } //（int m = 0; m <temp.length; m ++）{array [m+low] = temp [m]; }} / ** * Merge sort * * @param array * @return * / public static int [] sort（int [] array）{return sort（array、0、array.length -1）; } public static void main（string [] args）{int [] array = {3、5、2、6、2}; int [] sorted = sort（array）; System.out.println（ "最終結果"）; for（int i：sorted）{system.out.print（i + ""）; }}}テスト出力の結果：
最初の分離が実行され、[0-2] [3-4]が実行され、2番目の分離が実行され、[0-1] [2-2]が実行され、3回目の分離が実行され、[1-1] [1-1]がマージ：[0-0]および[1-1]は[0-1]と[0-1]とマージされます。 [3-3] [4-4]マージ：[3-3]および[4-4]マージ：[0-2]および[3-4]最終結果2 2 3 5 6
テスト後、例の結果と一致します。