マージソートとは何ですか？

配列を半分ずつに分割し、それぞれをソートしてからマージ（統合）する安定ソートアルゴリズム。最悪でもO(n log n)を保証するのが強み。

マージソートのポイントは？

配列を半分に分割し続け、要素1つになったら順番にマージしていく分割統治法。最悪・平均・最良すべてO(n log n)で安定した性能を発揮する。安定ソートなので同じ値の要素の順序が保たれる。追加メモリがO(n)必要な点がトレードオフ

【まーじそーと】

💡 「半分に割って、きれいに合体」を繰り返すだけで完璧に整列！

📌 このページのポイント

マージソートのイメージ → 分割してからマージで整列

ひよこ

マージソートってどうやって並べ替えるの？

ペンギン先生

まず配列を半分、そのまた半分…ってどんどん分けていくんだ。最後に要素が1つずつになったら、小さい順に「マージ（合体）」しながら戻していく。これで全体がきれいに並ぶよ

ひよこ

ペンギン先生

クイックソートは「分けるとき」に大小を仕分けるけど、マージソートは「合体するとき」に順番を決めるんだ。あとマージソートは安定ソートだから、同じ値の要素の並びが崩れないのが大きな違いだね

ひよこ

安定ソートってそんなに大事なの？

ペンギン先生

たとえば社員名簿を「名前順→部署順」でソートしたいとき、安定ソートなら部署でソートしても名前順が保たれるんだ。不安定ソートだと名前順がバラバラになっちゃうよ

ひよこ

デメリットってある？

ペンギン先生

マージ用の配列を別に作る必要があるから、メモリを余分にO(n)使うんだ。巨大なデータでメモリが限られてる場面では注意が必要だね

ひよこ

実際のプログラミングではどこで使われてるの？

ペンギン先生

PythonのTimsortやJavaのArrays.sort（オブジェクト型）はマージソートベースだよ。安定性が求められる場面では今でも第一選択肢なんだ。外部ソート（ファイルに収まらない大量データのソート）でもマージソートの考え方が基本になってるんだね

まとめ：ざっくりこれだけ覚えればOK！

「マージソート」って出てきたら「半分に分けて順番に合体する安定ソート」と思えればだいたいOK！

📖 おまけ：英語の意味

「Merge Sort」＝統合ソート

💬 1945年にジョン・フォン・ノイマンが考案したとされる、かなり歴史の古いアルゴリズムだよ