要素が一つになるまで分割し続ける

→高さはlognになる

それぞれのレベルで整列させながら統合していく

分割統治

統合の工程で労力を支払っている

それぞれのレベルでの統合は、それぞれの要素を1回処理すればいいので線形時間

よって実行時間は線形対数

最悪計算量もO(nlogn)

ランダムなデータではクイックソートの方が早い

安定ソートなので使われることはある