マージソート（まーじそーと）とは｜意味・使い方・読み方解説

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

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

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

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

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

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

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

IT

この用語ようごを学まなべるコンテンツ

関連かんれんする用語ようご

IT