マージソートまーじそーと

マージソート（Merge Sort）は、データをほぼ半分はんぶんに分割ぶんかつし、それぞれを 再帰さいき（再帰さいき）でソートしてから、整列せいれつ済ずみの 2 つをマージ（併合へいごう）して統合とうごうする分割ぶんかつ統治とうち型がたのアルゴリズムです。

観点かんてん	マージソート
計算けいさん量りょう（平均へいきん・最悪さいあく）	$O(N\log N)$（保証ほしょう）
安定あんてい性せい	安定あんてい（同値どうちの順序じゅんじょ保持ほじ）
追加ついかメモリ	必要ひつよう
用途ようと	外部がいぶソート・並列へいれつ処理しょり

最悪さいあくでも $O(N\log N)$ を保証ほしょうする点てんと、**同おなじ値ねの要素ようその順序じゅんじょが保たもたれる「安定あんていソート」**である点てんが強つよみです。データベースや、メモリに乗のり切きらないデータを扱あつかう外部がいぶソートで広ひろく使つかわれます。クイックソート と違ちがい追加ついかメモリが必要ひつようです。

試験しけんでは 「分割ぶんかつ→ソート→マージ」の流ながれと、安定あんていソートであること・最悪さいあくも $O(N\log N)$ である点てんが問とわれます。