マージソートについて

今回は、マージソートについて学習します。
マージソートとは、配列を繰り返し2分割していきます。
要素が1つになるまで細分化し、その後値の比較に入ります。

文章だとわかりづらいので、図で現してみます。

「84752613」の配列でやってみます。
まず全体の配列を2分割します。青で囲った部分です。

続いて2分割した中身を更に2分割します。
黄色で囲った部分です。

この状態で1度黄色枠を昇順に並び替えます。
並び替えた順がこちらです。

まず左の青枠「4857」を並び替えます。
この状態で、4と5を比較します。
小さいのが4なので、4が取り出されます。
次に8と5を比較して、5が取り出されます。
最後に8と7を比較して、7が取り出され、8が取り出されます。
これで、「4578」となりました。
次に青枠の2つ目、「2613」を見ていきます。
はじめに、2と1を比較します。
1が取り出されます。
次に、2と3を比較します。
2が取り出されます。
最後に6と3を比較します。
3が取り出されて、6が取り出されます。
こちらは、「1236」になりました。

「45781236」このようになりました。
青枠同士を比較していきます。

4と1を比較→1が取り出される。
4と2を比較→2が取り出される。
4と3を比較→3が取り出される。
4と6を比較→4が取り出される。
5と6を比較→5が取り出される。
7と6を比較→6が取り出される。
7と8を比較→7が取り出される。
最後に8が取り出される。

よって並び順が、「12345678」となります。