基本情報技術概論 (第７回) ３分でわかるマージソート埼玉大学理工学研究科堀山貴史 1 アルゴリズム：  マージソートソートされた２つの列 → １つにマージ（併合）するのは簡単（各列の先頭を見比べながら、小さい方を取っていく） 5 20 25 50  (併合ソート） 1 10 30 40 １回のマージの実行時間は、要素数に比例 2 アルゴリズム：マージソート (併合ソート） 5 25 50 20 30 40 10 1 5 25 50 20 5 25 5 25 5 25 30 40 10 1 50 20 50 20 20 50 30 40 30 40 30 40 分割 10 1 10 log n 段 1 1 10 マージ log n 段 1 段に O( n ) 時間 → 全部で O( n log n ) 時間 4 5 この教材のご利用について     この文面は、TOKYO TECH OCW の利用条件を参考にしましたこの教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。非商業利用に限定  この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。著作権の帰属  この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。同一条件での頒布・再頒布  この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件 6 この教材のご利用について  配布場所  http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/  この powerpoint ファイルの著作者  堀山貴史 2007-2009 [email protected]  改変等を加えられた場合は、お名前等を追加してください図の著作者  p. 2 ～ 3  堀山貴史  7