【Go言語でソートアルゴリズムを学ぶ】マージソート

マージソートとは

データを2分割する操作を繰り返し、要素数が1になるまで細分化します。細分化した要素の小さいものから先に新しい列に並べていくと整列できるという手法です。

平均的な計算量は O(nlogn)です。 一般的には安定なソートとして実装できますがランダムな配列に対してはクイックソートの方が高速です。

Go言語でのコード例は以下の通りです。

Embedded content: https://gist.github.com/sena-anny/0840b646545fbc803fa7bd822339975a

数字の配列を２分割していきます。

分割された数字を先頭から比較して小さい順に新しい配列に入れていきます。（マージ）

例）初期状態: [2, 1, 5, 4, 3]

1回目：　　 配列を[2, 1]と [5, 4, 3]に分割します。

2回目：　　 さらに[2]と[1]（分割終了）、[5]と[4, 3]に分割します。

3回目: 　[2]と[1]と[５]と[４]と[3]に分割されます。

4回目: 　[2]と[1]から[1, 2]に、[４]と[3]から[3, 4]にマージします。

5回目: 　[5]と[3, 4]から[3, 4, 5]にマージします。

6回目： [1, 2]と[3, 4, 5]から[1, 2, 3, 4, 5]にマージします。

以上から[1, 2, 3, 4, 5]に並べ替えられます。