Javaの場合

1. マージソートはソートアルゴリズムです
2. マージソートは、1945年にジョンフォンノイマンによって作成されました
3. マージソートは、分割統治法を使用 して配列内の要素をソートします

1. 分割統治法は問題を解決するためのアプローチです
2. 分割統治法には3つのステップがあります
   。1。分割統治法：与えられた問題をサブ問題に分割します
   。2。征服：サブ問題を解決します。3
   。結合：答えを適切に結合します。

マージソートの学習を始めましょう

まず、マージソートの動作を確認します

ここで、赤い
色は- >分割を意味し、緑の色は->征服を意味します

マージソートアルゴリズムの段階的な内訳

1）数字の配列を取る

2）
ここで、この配列の中央を取ります。この場合
、この配列のサイズは7です。
したがって、開始インデックスと終了インデックスはそれぞれ0と6になります。ここで、配列の中央
を見つけるために、次の簡単な式があります：（l + r）/2。ここで、 lはこの配列の左側であり、配列の開始= 0です。rはこの配列の右側であり、= a.length-1 = 7–1=6です。

mid = （l + r）/ 2
mid =（0 + 6）/2=
インデックス「3」の3要素は3

3）配列を左右の配列に分割します。各配列に要素が1つだけ残るまで配列を分割します。つまり、 l <r

配列に要素が1つしかない場合は、配列が並べ替えられていることを意味します

配列の分割が実際に行われているのを見てみましょう

注：l、r、midではfloat値を使用していません

注：これらは、l、r、midが指しているインデックスです。

ステップ1：

l = 0
r = a.length-1 = 6
mid =（l + r）/ 2 = 3

これが「左」と「右」の2つの配列です

「左」配列のサイズは次のとおりです。 （mid-l）+1
（3–0）+ 1 = 4

「右」配列のサイズは次のとおりです。 （r-mid）
（6–3）= 3

left [] = {28、27、43、3}
right [] = {9、82、10}

上記のポイント（3）で説明したように、
「各配列に要素が1つだけ残るまで配列を分割します」

ステップ2：

次に、「左」配列を分割します

l = 0
r = a.length-1 = 3
mid =（l + r）/ 2 = 1

これが「左」と「右」の2つの配列です

「左」配列のサイズは次のとおりです。 （mid-l）+1
（1–0）+ 1 = 2

「右」配列のサイズは次のとおりです。 （r-mid）
（3–1）= 2

left [] = {38、27}
right [] = {43、3}

ステップ3：

次に、「正しい」配列を分割します

l = 0
r = a.length-1 = 2
mid =（l + r）/ 2 = 1

これが「左」と「右」の2つの配列です

「左」配列のサイズは次のとおりです。 （mid-l）+1
（1–0）+ 1 = 2

「右」配列のサイズは次のとおりです。 （r-mid）
（2–1）= 1

left [] = {9、82}
right [] = {10}

このように、これらの配列を左右に分割しました

最終的に分割された配列を分割した後はこれです

次に、これらのソートされた配列をマージします

これらの配列はどのようにソートされますか？

配列に含まれる要素が1つだけの場合、これらすべての配列が並べ替えられていることは明らかです。

マージは、並べ替えられた配列を1つの並べ替えられた配列に結合するプロセスです。ここでは、2方向のマージ手段を使用しました。つまり、4つの配列がある場合、最初の2つを並べ替え、次に2番目の2つを並べ替えてから、両方の並べ替えられた配列の結果を並べ替えます。

では、これらのソートされた配列をマージしましょう

「マージのプロセス」

左右の配列のサイズを見つける

mid =（l + r）/ 2

leftArraySize =（mid-l）+1

rightArraySize =（r-mid）

左の配列と右の配列でそれぞれポインタiとjを取ります。
メイン配列の次の要素を格納する場所を指すためのポインタk=l （ここではl =配列の左側）を取ります（ aという名前のメイン配列を取りましょう）

今チェック

1）left [i] <right [j]の場合、a [k] =left[i]の場合

2）次にkとiをインクリメントします

3）else a [k] = right [j]

4）次にkとjをインクリメントします

までこれらの4つのステップを繰り返します

i <leftArraySize && j <rightArraySize

この条件が満たされ、ループが停止しても配列に残りの要素が残っている場合はどうなりますか？このために、配列から残りの要素をコピーします（要素が残っています）

やあ！マージが行われます

アレイのマージの動作を見てみましょう

ここでは、2つの配列
が残っています={38}
右={27}

上記のプロセスを使用してそれらをマージしました

a [] = {27、38}

さて、複雑な例を見て理解しましょう

左={27、38}
右= {3、43）

i = 0
j = 0
k = l

今のところkを忘れると、コードで理解できます

ステップ1：

left [i]=27およびright[j]= 3

left [i] <right [j] = false
right [j] <left [i] = true

a [k] = right [j]
j++およびk++

a = {3}

ステップ2：

left [i]=27およびright[j]= 43

left [i] <right [j] = true
right [j] <left [i] = false

a [k] = left [i]
i++およびk++

a = {3、27}

ステップ3：

left [i]=38およびright[j]= 43

left [i] <right [j] = true
right [j] <left [i] = false

a [k] = left [i]
i++およびk++

a = {3、27、38}

これで、両方の配列の最後に到達した
ので、残りのすべての要素を右側の配列からメイン配列にコピーするだけです。

a = {3、27、38、43}

このように、残りのすべての左右の配列をマージしました

結果は次のようになります

これで、マージソートの概念的な部分が完了しました。

これがマージソートアルゴリズムのコードです

マージソートコードの例

マージソートの重要な特徴：

• マージソートはインプレースアルゴリズムではありません。ソートを実行するには補助配列が必要です
• マージソートの時間計算量はO（N log N）—基数2です。分割フェーズ中に配列を半分に繰り返し分割しています
• マージソートは、リンクリストのソートに役立ちます。
• マージソートは安定したソートです。つまり、配列内の同じ要素が相互に元の位置を維持します。
• マージソートのスペースの複雑さはO（n）です。これは、このアルゴリズムが多くのスペースを必要とし、最後のデータセットの操作を遅くする可能性があることを意味します。

この記事を読んでくれてありがとう️

クリシュナワドワニ脚本の作品