【まーじそーと】
マージソート とは？
最終更新:
💡 「半分に割って、きれいに合体」を繰り返すだけで完璧に整列！
データを分割し、各部分を整列してからマージ（併合）するソートアルゴリズム。基本的な配列実装では最悪でもO(n log n)で整列できる。同じ値なら左側を先に取り出すことで安定性を保つ。
📌 このページのポイント
ひよこ マージソートってどうやって並べ替えるの？
ペンギン先生 上から分ける方式なら、配列を半分、そのまた半分と分けて、要素1つずつにするよ。そのあと、整列済みの2つの部分の先頭を比べ、小さい方から取り出して合体する。図の8・3・5・1・6・2も、最後には1・2・3・5・6・8になるんだ。
ひよこ クイックソートとどう違うの？
ペンギン先生 ひよこ 安定ソートってそんなに大事なの？
ペンギン先生 同じ値のときは、元の左側の要素から取り出して併合すると、同じ値同士の順番が保たれるよ。社員名簿を名前順にしたあと部署で安定ソートすれば、同じ部署の中で名前順が残る。不安定な方式では、その順番が変わることがあるんだ。
ひよこ デメリットってある？
ひよこ 実際のプログラミングではどこで使われてるの？
ペンギン先生 Pythonのリストのソートは、整列済みの並びを見つけて併合する、適応的で安定なマージソートがもとになっているよ。いつも単純に半分へ分割するわけではなく、入力にある順序を活用しているんだ。
まとめ：ざっくりこれだけ覚えればOK！
「マージソート」って出てきたら「分けて整列し、小さい順に合体するソート」と思えばだいたいOK！
📖 おまけ：英語の意味
「Merge Sort」 ＝ 併合ソート
💬 Mergeは併合、Sortは並べ替えのこと。整列済みの部分を併合して、全体を並べ替える仕組みを表すよ。