差分ソートアルゴリズム「刹那式」の紹介（ベンチマークあり）

# 刹那式
刹那式（せつなしき）は、二分挿入ソートを応用した、差分ソートです。
ソート済み配列に対し、値の変更を行った箇所に焦点を当て、超高速にソートします。

以下の特徴があります。

* 比較ソート
* 安定ソート
* 外部領域：無し
* 平均時間：比較O(log N)、移動O(N/2)
* 最悪時間：比較O(log N)、移動O(N)
* 最良時間：比較O(2)、移動O(0)
* 再帰：無し


# リポジトリ
[刹那式（せつなしき） Unlicense](https://github.com/EmuraDaisuke/SortingAlgorithm.SetsunaShiki)


# 基本となるアルゴリズム
* ソート済み配列に対して、任意の位置の値を変更します。
* （変更位置の値 ＜ 変更位置の下の値）であれば、下方を二分探索し、変更位置から探索位置を回転します。
* （変更位置の上の値 ＜ 変更位置の値）であれば、上方を二分探索し、変更位置から探索位置を回転します。

## 具体的な流れ
~~~
ソート済み配列に対して、任意の位置の値を変更します
0 1 2 4 5 6 7 9|ソート済み配列
        ↓
0 1 2 4 x 6 7 9|任意の位置の値を変更
~~~
~~~
（変更位置の値 ＜ 変更位置の下の値）であれば、下方を二分探索し、変更位置から探索位置を回転します
0 1 2 4 5 3 7 9|[5]=3の場合
0 1 2 4 5|. . .|下方を二分探索
. . .|3 4 5|. .|変更位置から探索位置を回転
0 1 2 3 4 5 7 9|ソート結果
~~~
~~~
（変更位置の上の値 ＜ 変更位置の値）であれば、上方を二分探索し、変更位置から探索位置を回転します
0 1 8 4 5 6 7 9|[2]=8の場合
. . .|4 5 6 7 9|上方を二分探索
. .|4 5 6 7 8|.|変更位置から探索位置を回転
0 1 4 5 6 7 8 9|ソート結果
~~~


# ビルド＆テスト
環境は以下のとおりです。

* Windows 10 Pro 64bit
* Core i7-8700 3.20GHz

## **Msvc**
Microsoft(R) C/C++ Optimizing Compiler Version 19.15.26732.1 for x64
Microsoft (R) Incremental Linker Version 14.15.26732.1

~~~sh
cl Main.cpp -Ox -EHsc -Fe:TestMsvc.exe
TestMsvc.exe
~~~

## **clang++**
clang version 7.0.0 (tags/RELEASE_700/final)
Target: x86_64-w64-windows-gnu

~~~sh
clang++ Main.cpp -O3 -o TestClang++.exe
TestClang++.exe
~~~

## **g++**
gcc version 8.2.0 (Rev3, Built by MSYS2 project)
Target: x86_64-w64-mingw32

~~~sh
g++ Main.cpp -O3 -o TestG++.exe
TestG++.exe
~~~


# 平均ベンチマーク
以下は、ソート済み配列に対し、ランダムな位置を、ランダムな値に変更した場合です。
単位は秒で、数値が低いほど高速です。

## **Msvc**
|件数|std::sort|std::stable_sort|刹那式|
|---:|---:|---:|---:|
|10,000|0.00007095|0.00004502|**0.00000115**|
|1,000,000|0.00975892|0.00698905|**0.00009487**|
|100,000,000|0.27018098|1.26169269|**0.01670523**|

## **clang++**
|件数|std::sort|std::stable_sort|刹那式|
|---:|---:|---:|---:|
|10,000|0.00006162|0.00006669|**0.00000050**|
|1,000,000|0.00775640|0.00978430|**0.00006938**|
|100,000,000|0.99487866|1.46673092|**0.01248609**|

## **g++**
|件数|std::sort|std::stable_sort|刹那式|
|---:|---:|---:|---:|
|10,000|0.00009420|0.00006123|**0.00000040**|
|1,000,000|0.01269281|0.00870394|**0.00006129**|
|100,000,000|1.32669707|1.32506381|**0.01232715**|


# 特性ベンチマーク
以下は全て、「100,000,000」件でソートしました。
単位は秒で、数値が低いほど高速です。

## 最悪ケース１
ソート済み配列に対し、先頭を最大値に変更した場合です。

||std::sort|std::stable_sort|刹那式|
|---:|---:|---:|---:|
|Msvc|0.28328255|1.27838705|**0.03301556**|
|clang++|0.94680632|1.49072315|**0.02450915**|
|g++|1.24406811|1.35104790|**0.02465655**|

## 最悪ケース２
ソート済み配列に対し、末尾を最小値に変更した場合です。

||std::sort|std::stable_sort|刹那式|
|---:|---:|---:|---:|
|Msvc|0.29024827|1.27097092|**0.03784692**|
|clang++|6.59369224|1.44779880|**0.02844831**|
|g++|7.05050788|1.30785120|**0.02579642**|

## 最良ケース
ソート済み配列に対し、値を変更せずに、位置をランダムにした場合です。

||std::sort|std::stable_sort|刹那式|
|---:|---:|---:|---:|
|Msvc|0.26143167|1.24644350|**0.00000026**|
|clang++|0.99570890|1.44735863|**0.00000031**|
|g++|1.33114203|1.30589223|**0.00000050**|


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

ソートは、常に全体で行う必要はないという観点から、差分ソートという考えに至ったアイデアです。
本来であれば、全体ソートである std::sort と std::stable_sort との比較はフェアではないのですが、差分ソートの有用性を判断していただくには必要かと思い、ベンチマークを掲載することにしました。
参考になれば幸いです。

上手く運用すれば、激速なパフォーマンスが得られますが、使い方を誤ると激遅になる諸刃の剣。

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

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