マージソート
すでにソート済みのデータを併合(マージ)して新たな整列されたデータを取得するアルゴリズム
以下、手順
全データを要素1の小さな配列に分解する
2つの要素数1の配列同士をマージすることで要素数2のソート済みの配列ができる
2つの要素数2の配列同士をマージすることで要素数4のソート済みの配列ができる
これを繰り返して全体がソート済みの配列を得ることでソート完了
計算量について
マージ回数は、配列の要素数が2,4,8…と繰り返すことからlogn回
1回のマージでn回の比較が必要であるから全体としての計算量はO(nlogn)となる
関連記事