マージソートの仕組みと流れ4つ｜言語別のマージソートサンプル

システム
エンジニア

マージソートとはどんなアルゴリズムなのですか？

プロジェクト
マネージャー

データ列を最小数まで分割し、それぞれのデータ列をソートした後にマージを行うアルゴリズムです。

マージソートとはどんなアルゴリズム？

マージソートの基本的なアルゴニズム手順は、不規則なデータ列を最小数の配列まで分割（通常は二等分）し、分割した各データ列にデータが1個含まれるならそれを返し、ソートされたデータ列（1個の場合はそれ自身）をマージ（併合）します。

分割した各データ列にデータが2個以上含まれる時は、データ列の分割から2つのソートされたデータ列をマージするところまで再帰的に適用してマージソートします。

マージソートの仕組みと流れ4つ

マージソートは、不規則配列の数値を小さい配列に分解してから順に併合し、2つの配列の先頭から小さい数値を抽出して新しい配列生成を完了させる、といった流れ・仕組みでソートを行っていきます。以下に、それぞれの過程をご紹介していきます。

マージソートの仕組みと流れ1：不規則配列の数値を小さい配列へ分解

マージソートではまず、不規則の配列にある数値を小さい配列へ分解していきます。小さい配列に分解するというのは、配列に8個の要素値があるなら、それぞれ4つずつの要素値を含む配列に分解するといったことです。

つまり、要素値同士を比較して並び替えが容易に行えるよう、1つの配列に含まれる要素値の数を少なくしていくということです。言葉で説明するのは難しいものですが、どういったことなのか以下を参考にしてください。

各配列をほぼ2分割する

まずは、初期データのデータ配列を2分割します。例として、初期データが54786123だとすれば、5478と6123に分割します。

完全な2分割ではなく、ほぼ2分割になるケースは、初期データのデータ配列にある要素数の数が偶数ではない時です。547861239といったように偶数ではない時は、5478と61239（あるいは54786と1239）といった感じで、ほぼ2分割にする形で問題ありません。

要素数1まで分解する

5478と6123に2分割できたら、もう2回ほど2分割して要素数1まで分割を行っていきます。まず、左側5478は54と78に分け、右側6123は61と23に分けます。そして、54を5と4、78を7と8、61を6と1、23を2と3に分割します。

ここまでが、データ列の分解作業になります。要素数1まで分割するというのは、1つのデータ列に含まれる要素数の数が1つになるまで分解するということです。

マージソートの仕組みと流れ2：順に併合していく

全てを要素数1まで分解したら、順に併合していきます。まず、もともと同じ配列に要素数2として存在していた要素値たちを組み合わせから併合していきます。

54は前回の分解で5と4に分けましたが、マージソートでは小さい数を先に持ってくる必要があるので、今回の過程で5と4を併合する時には結果として45になります。同じように7と8は併合すると18になり、6と1は16、2と3は23になります。

マージソートの仕組みと流れ3：2つの配列の先頭から小さい数値を抽出

上記で併合した45・78・16・23を、初期データを分割した左側と右側でそれぞれ併合します。ここでの併合作業は2つの配列の先頭から小さい数値を抽出することで、簡単にソートすることができます。

左側の45と78であればそれぞれの先頭にある4と7を比べ、小さい方（例では4）を抽出します。次に5と7を比べて小さい方（5）を抽出し、残りも小さい順に併合していくと4578になります。右側は1236になります。

マージソートの仕組みと流れ4：新しい配列の生成の完了

左側4578・右側1236の配列を、1つに整列させます。数値が小さい順に抽出する必要があるので、それぞれにある全体の数値を比べながら整列されていきます。

最も小さい数値は1なので、まずは右側の1を抽出します。それから順を追って同じ右側の2と3を抽出し、3に続く数値の左側4を抽出します。そういった流れで5・6・7・8と抽出していけば、12345678に整列された新しい配列が生成されます。

言語別のマージソートサンプル5つ

実際に取り掛かる際の参考までに、言語別のマージソートサンプルをご紹介します。ご紹介するのは、java・C言語・C++・GO・Pythonのマージソートサンプルです。

人により書き方が異なるプログラミング言語もあるため、様々なマージソートサンプルを見てみたい方は、検索をかけてみると他のサンプルも見つけることができます。今回ご紹介しているマージソートサンプルは一例として、独自に調べてみると良いでしょう。

マージソートサンプル1：java

java（ジャヴァ）は1995年に開発された汎用プログラミング言語で、クラスベースのオブジェクト指向の実装依存関係を極力少なくするよう設計されています。

クライアント・サーバ型のWEBアプリケーションで用いられる言語の中でもっとも人気があり、900万人もの開発者がいると報告されています。そんなjavaのマージコードサンプルには、以下のようなものがあります。

マージソートサンプル2：C

C言語は1972年にデニス・リッチー氏が主体となって開発された汎用プログラミング言語で、汎用性の高さとプログラムの自由度に優れています。

ソースコードの再利用性・メンテナンス性・目的に合った拡張の容易性といった面でも使いやすいため、多くの分野に適応しています。そんなC言語のマージソートサンプルには、以下のようなものがあります。

マージソートサンプル3：C++

C＋＋は1983年にビャーネ・ストロヴストルップ氏が開発した汎用プログラミング言語で、日本語の会話の中では通称シープラまたはシープラプラと呼ばれます。

派生元のC言語が持つ機能と特徴を継承しながら、表現力と効率性が向上された仕様となっています。そんなC＋＋のマージソートサンプルには、以下のようなものがあります。

マージソートサンプル4：GO

GO言語は、2009年にRobert Griesemer氏とロブ・パイク氏とケン・トンプソン氏によって設計されたプログラミング言語です。

名称はGolangやGO言語で扱われることもありますが、正式にはGoと表記します。比較的新しい言語のGO、そのマージソートサンプルには以下のようなものがあります。

マージソートサンプル5：Python

Python（パイソン）は1991年にグイド・ヴァンロッサム氏が開発した汎用プログラミング言語で、扱いやすいコードになるようシンプルな設計になっています。

C言語よりも様々なプログラムを少ないコードで書ける上、分かりやすく勉強しやすいという利点があります。幅広く用いられるPythonのマージソートサンプルには、以下のようなものがあります。

マージソート以外のソートアルゴリズム6つ

ソートアルゴリズムには、マージソート以外にもたくさんの種類が存在しています。

全部で10を超える種類がある中から、比較的に一般的なバブルソート・バケットソート・基数ソート・ヒープソート・ノームソート・クリックソートをご紹介します。

それぞれに違った特徴があり、ソートする方法も異なるので、違いを学ぶことでその時々に応じたソートアルゴリズムを選べるようになるでしょう。

ソートアルゴリズム1：バブルソート

バブルソートとは、配列要素を最初から最後まで見て、順序が逆の要素があったら入れ替える、ということを全ての要素の順序が整うまで繰り返すソートアルゴリズムです。

並べ替えの中でデータが下から上に移動する様子を浮かぶ泡に例えて、バブルソートという名前が付けられました。ソートアルゴリズムの中では最も直観的で、理解しやすいと言われています。

ソートアルゴリズム2：バケットソート

バケットソートは、配列内の要素値をインデックスとしてあらかじめ用意したバケツに直接移動し、バケツ手前から順番に配列に戻していくソートアルゴリズムです。

用意するバケツの数は配列内にある要素値の数と同じで、たとえば要素値が100個あるならバケツも100個用意します。バケットソートはデータの存在範囲が有限個に限定されていないと使うことができませんが、使える場合は高速な並び替えを行える有用なアルゴリズムになります。

ソートアルゴリズム3：基数ソート

基数ソートはバケットソートの変形型で、要素の小さい位から見ていき、対応する数字でバケットソートを行う（バケツに移動させる）ソートアルゴリズムです。

まず要素の1の位でバケットソートし、次に10の位、その次に100の位でバケットソートする、といったように行っていきます。バケットソートと基数ソートの違いを比べた場合、基数ソートの方がバケットソートよりもメモリ使用量が少ないという利点が挙がります。

ソートアルゴリズム4：ヒープソート

ヒープソートは、配列をヒープ構造にしてから根元ノードの数字を取り出し、再びヒープ構造にしてから根元ノードの数字を取り出すことを全数字を取り出すまで行うソートアルゴリズムです。

ヒープ構造とは、二分木の各ノードにデータを保持し、二分木のうちの親ノードが2つの子より小さくなるよう作られたデータを言います。ソート過程の特徴として、二分木の根には必ず最大値がきて、各親子関係の親ノードには必ず最大値がきます。

ソートアルゴリズム5：ノームソート

ノームソートは、配列の要素を順方向に順番に見ていき、順序が逆の要素を見つけたら掴んで手前にずらし、交換後も順序が逆ならまたその手前にずらし、ずらし終わったらそこから順方向へ要素を見て最初と同じようにする、ということを繰り返すソートアルゴリズムです。

配列最後の要素までずらし終わったら、ソートは完了になります。

ソートアルゴリズム6：クイックソート

クイックソートは、配列内でピボットとして要素を1つ選び、ピボットより左側の全要素は小さく、右側の全要素は大きくなるよう互いに入れ替えていき、ピボット左側から新しいピボットを選び先ほどと同じことを行い、次に右側からも新しいピボットを選び先ほどと同じことを行うことを繰り返すソートアルゴリズムです。

データの比較と交換の回数がとても少なく、データがバラバラでも効率的な並び替えが実行できると言われています。

システム
エンジニア

マージソート以外にも様々なソートがあるのですね。

プロジェクト
マネージャー

そうですね。それぞれのソートに特徴やメリット、デメリットがあるので、状況に応じて使い分けれるように勉強していきましょう。

マージソートの仕組みを理解しよう

マージソートは、簡単に言えば分解してから併合していくソートアルゴリズムです。比較的早く使えるので、その仕組みを理解し、適していると判断できる時には使ってみましょう。

また、他のソートアルゴリズムと比較することで、何が良いのか・何が悪いのか・そのソートアルゴリズムの特徴は何なのかが見えてきます。はじめにソート全体の勉強を行うことが大事であり、そこからソート個々について詳しく見ていくと良いでしょう。