マージソート

手順

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

→高さはlognになる

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

概要

分割統治

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

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

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

最悪計算量もO(nlogn)

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

table:性能

計算量 O(nlogn)

安定ソート ⭕

内部ソート ❌