高速な比較安定ソートアルゴリズム「颯式」の紹介（ベンチマークあり） - Qiita颯式（はやてしき）は、「クイックソート種より高速」を目指した、マージソートの改良アルゴリズムです。 以下の特徴があります。 比較ソート 安定ソート 外部領域：N 最良：O(N) 平均：O(N log N) 最悪：O(N log N) 再帰：無し リポジトリ 颯式（はやてしき） MIT License 基本となるアルゴリズム 外部領域を、2Nの連続帯として見立てます。 値を外部領域に置く際、以下のルールを適用します。 （最大値 ≦ 値）であれば、昇順列の上側に置き、最大値を更新します。 （値 ＜ 最小値）であれば、降順列の下側に置き、最小値を更新します。 （最小値 ≦ 値 ＜ 最大値）であれば、新しい値（最大値であり最小値）を昇順列に置き、それまでに並べた値群をPartとします。 Part群をマージします。 具体的な流れ 外部領域を、2Nの連続帯として見立てます 4 5 1 2 7 6 3
