焔式

焔式（ほむらしき）は、マージソートを応用した、差分ソートです。
ソート済み配列に対し、値の変更を行った箇所に焦点を当て、高速にソートします。

以下の特徴があります（変更範囲をDとして）。

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

リポジトリ

焔式（ほむらしき） Unlicense

基本となるアルゴリズム

ソート済み配列に対して、任意の範囲の値を変更します。
変更範囲を、比較安定ソートします。
「前方範囲、変更範囲、後方範囲」で三区画マージします。

具体的な流れ

ソート済み配列に対して、任意の範囲の値を変更します
0 2 3 4 5 6 7 9|ソート済み配列
    ↓ ↓ ↓
0 2|8 1 3|6 7 9|

変更範囲を、比較安定ソートします
0 2|8 1 3|6 7 9|
    ↓ ↓ ↓
0 2|1 3 8|6 7 9|

「前方範囲、変更範囲、後方範囲」で三区画マージします
0 2|1 3 8|6 7 9|

02   前方範囲
138  変更範囲
679  後方範囲

012    前方範囲を消費するまで、変更範囲とマージ（前方Part）
36789  変更範囲の残りと、後方範囲をマージ（後方Part）

01236789  前方Partと後方Partを連結（ソート完了）

ビルド＆テスト

検証を行った環境は以下のとおりです。

Windows 10 Pro 64bit
Core i7-8700 3.20GHz

颯式と刹那式が兄弟ディレクトリに存在する状態でビルドできます。

Msvc

Microsoft(R) C/C++ Optimizing Compiler Version 19.16.27027.1 for x64

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

clang++

clang version 8.0.0 (tags/RELEASE_800/final)
Target: x86_64-w64-windows-gnu

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

g++

gcc version 8.3.0 (Rev2, Built by MSYS2 project)
Target: x86_64-w64-mingw32

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

平均ベンチマーク

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

Msvc

件数	std::sort	std::stable_sort	焔式
10,000	0.00031643	0.00016890	0.00014270
1,000,000	0.05004999	0.02833382	0.02414271
100,000,000	3.43509980	3.48550165	2.55574413

clang++

件数	std::sort	std::stable_sort	焔式
10,000	0.00027717	0.00020017	0.00015642
1,000,000	0.03866672	0.02881882	0.02255046
100,000,000	3.38201222	3.64178056	2.60998679

g++

件数	std::sort	std::stable_sort	焔式
10,000	0.00029155	0.00020019	0.00014887
1,000,000	0.04052708	0.02760306	0.02054782
100,000,000	3.58270940	3.45231729	2.36870185

特性ベンチマーク

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

最良ケース

ソート済み配列に対し、値を変更せずに、範囲をランダムにした場合です。

	std::sort	std::stable_sort	焔式
Msvc	0.23993706	1.30073792	0.01059685
clang++	1.04052412	1.52173567	0.01611595
g++	1.34400042	1.31273356	0.01510180

余談

如何だったでしょうか？

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

工夫をすれば、より高速にソートできることが示せたと思います。
運用の目安としては、(D ＜ (N/2))の場合は差分ソート、そうでなければ全体ソートが良いかなという所感です。

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

以下の記事も併せて読んでいただけると、より楽しめるかも知れません。