【マージソート法とは】リストの昇順・降順ソートの原理と計算量

マージソート法とは?リストを昇順・降順ソートする原理・アルゴリズムについて解説します。

[latexpage]

スポンサーリンク

【マージソート法とは】リストを昇順・降順ソート

マージソート法とは、整列アルゴリズムの1つです。
整列されていないリストを2つのリストに分割します。
次に部分リストを整列させた後、それらを結合(マージ)することで、整列済みの1つのリストにします。

特徴
最悪計算量O(n log n)と小さい(高速だが、完全にランダムなリストに対してはクイックソートの方が速い)。
安定なソートとなる。
スポンサーリンク

【プログラミング】マージソートの実装

プログラミング言語でマージソートを実装する方法については、言語別に下記事で紹介しています。

詳細記事
1 【Python】マージソート法を実装
おすすめ記事
1 【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
2 【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験
IPA試験対策
スポンサーリンク

コメント