高速な比較安定ソートアルゴリズム「颯式」の紹介（ベンチマークあり）

# 颯式
颯式（はやてしき）は、「クイックソート種より高速」を目指した、マージソートの改良アルゴリズムです。

以下の特徴があります。

* 比較ソート
* 安定ソート
* 外部領域：N
* 最良：O(N)
* 平均：O(N log N)
* 最悪：O(N log N)
* 再帰：無し


# リポジトリ
[颯式（はやてしき） MIT License](https://github.com/EmuraDaisuke/SortingAlgorithm.HayateShiki)


# 基本となるアルゴリズム
* 外部領域を、2Nの連続帯として見立てます。
* 値を外部領域に置く際、以下のルールを適用します。
  * （最大値 ≦ 値）であれば、昇順列の上側に置き、最大値を更新します。
  * （値 ＜ 最小値）であれば、降順列の下側に置き、最小値を更新します。
  * （最小値 ≦ 値 ＜ 最大値）であれば、新しい値（最大値であり最小値）を昇順列に置き、それまでに並べた値群をPartとします。
* Part群をマージします。

## 具体的な流れ
~~~
外部領域を、2Nの連続帯として見立てます

4 5 1 2 7 6 3 8|入力列
. . . . . . . .|外部領域
→昇順列  降順列←|実際

               |4 5 1 2 7 6 3 8|入力列
. . . . . . . . . . . . . . . .|外部領域
        降順列←｜→昇順列        |2N見立て
~~~
~~~
新しい値（最大値であり最小値）を昇順列に置く
               |. 5 1 2 7 6 3 8
. . . . . . . . 4 . . . . . . .
~~~
~~~
次の値は（最大値 ≦ 値）なので、昇順列の上側に置き、最大値を更新
               |. . 1 2 7 6 3 8
. . . . . . . . 4 5 . . . . . .
~~~
~~~
次の値は（値 ＜ 最小値）なので、降順列の下側に置き、最小値を更新
               |. . . 2 7 6 3 8
. . . . . . . 1 4 5 . . . . . .
~~~
~~~
次の値は（最小値 ≦ 値 ＜ 最大値）なので、新しい値（最大値であり最小値）を昇順列に置く（Part：145が完成）
               |. . . . 7 6 3 8
. . . . . . .|1 4 5|2 . . . . .
~~~
~~~
次の値は（最大値 ≦ 値）なので、昇順列の上側に置き、最大値を更新
               |. . . . . 6 3 8
. . . . . . .|1 4 5|2 7 . . . .
~~~
~~~
次の値は（最小値 ≦ 値 ＜ 最大値）なので、新しい値（最大値であり最小値）を昇順列に置く（Part：27が完成）
               |. . . . . . 3 8
. . . . . . .|1 4 5|2 7|6 . . .
~~~
~~~
次の値は（値 ＜ 最小値）なので、降順列の下側に置き、最小値を更新
               |. . . . . . . 8
. . . . . . 3|1 4 5|2 7|6 . . .
~~~
~~~
次の値は（最大値 ≦ 値）なので、昇順列の上側に置く（Part：368が完成）
               |. . . . . . . .
. . . . . .|3|1 4 5|2 7|6 8|. .
~~~
~~~
最終的な外部領域
4 5|2 7|6 8|. .  昇順列見立て
. . . . . .|3|1  降順列見立て
4 5|2 7|6 8|3|1  実際の内容
~~~
~~~
生成したPart群をマージします  
145  27  368  
12457  368  
12345678  
ソート完了  
~~~


## 改良
基本アルゴリズムから更に、以下の改良を施します。

* Partの長さを確保する為、インサートソートを行います。
* 再帰をしないように、逐次マージを行います。


# 検証を行った環境
* Windows 10 Pro 64bit
* Core i7-8700 3.20GHz
* Microsoft(R) C/C++ Optimizing Compiler Version 19.16.27030.1 for x64
* clang version 8.0.0 (tags/RELEASE_800/final)
* gcc version 8.3.0 (Rev2, Built by MSYS2 project)


# 乱数ベンチマーク
同じシードから生成したfloat値をソートしました。
単位は秒で、数値が低いほど高速です。
![Random_10000.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/379361/4e82765c-2b15-9334-063c-6ca2e0894472.png)
![Random_1000000.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/379361/530577cd-a21e-9d32-d801-3ca85a675cc5.png)
![Random_100000000.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/379361/caed6f1f-1ff4-a798-66fc-187949451596.png)


# 特性ベンチマーク
以下は全て、float値「100,000,000」件でソートしました。
単位は秒で、数値が低いほど高速です。
![Msvc.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/379361/8af35731-e0e7-f346-792c-f3944345c82f.png)
![clang++.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/379361/16872a88-51ec-00d0-31eb-44f0994cd23c.png)
![g++.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/379361/bbca437a-7977-e03f-159a-db5977506f79.png)


# 余談
如何だったでしょうか？

颯式は、安定ソートでありながら、乱数に強いことが窺えます。
特性ベンチマークでは、アルゴリズム特性ではなく、コンパイラの最適化特性の影響が強く出てしまう為、ほとんど判断材料にならないことが分かりました。

マージソート種がクイックソート種に勝てる日は来るのでしょうか？

ソートアルゴリズムには、まだ浪漫が残っています。

---
以下の記事も併せて読んでいただけると、より楽しめるかも知れません。
* [「新手法の提案：差分ソートアルゴリズム「刹那式」の紹介（ベンチマークあり）」](https://qiita.com/EmuraDaisuke/items/292097634e73d43f353a)
* [「高速な差分ソートアルゴリズム「焔式」の紹介（ベンチマークあり）」](https://qiita.com/EmuraDaisuke/items/8b3812a4020e20b00100)