闇の力を駆使すればO(1)でスターリンソートなぞ容易いものよ

そう...**Template**ならね！！！

# スターリンソートとは
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる</p>&mdash; やんぎん (@4116You) <a href="https://twitter.com/4116You/status/1155619860027547648?ref_src=twsrc%5Etfw">July 28, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

なんと$O(N)$でソートが終了するという、実行速度にハートフルでピースフルなアルゴリズムです。
ピースフルなのでソート順に並んでいない要素は粛清されます。

## 公式リポジトリ
スターリンソートは素晴らしいアルゴリズムなので、なんと公式リポジトリが存在します。
素敵:relaxed:
https://github.com/gustavo-depaula/stalin-sort

## 先駆者達
[計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell](https://qiita.com/Tatsuki-I/items/380d6bd06515b872b2b2)
[計算量O(n)で噂のスターリンソートを実装してみた](https://qiita.com/MeilCli/items/721526d716851e92192a)
[[Rust] スターリンソートと PartialOrd](https://qiita.com/osanshouo/items/1d4f56d93ee8ac8bdf55)
[rubyでスターリンソートをやってみた（ブロック渡しも可能）](https://qiita.com/haru_pad/items/1598690e1105f3e33389)
[スターリンソート in perl](https://qiita.com/DQMerA/items/a8cc1588a6e3268ce9ce)
[話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した](https://qiita.com/Sirloin/items/c9e5c74be3366df65bce)
[Pythonワンライナーでスターリンソート](https://qiita.com/LouiS0616/items/cf0c41d42fc9910df587)

# 更に高みへ
コンパイルタイムで計算すれば$O(1)$なのでは？と思ったので実装しました。:sunglasses:

# 実装
若干余計なコードが含まれているかもしれない

```cpp
#include <iostream>
#include <utility>

template<int...Seq>
using seq = std::integer_sequence<int, Seq...>;

template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01;


template <class Result>
struct stalin_sort_stopper {
	using result = Result;
};
// nextを展開するwrap
template<class Result, int CompTarget, int...Next>
constexpr stalin_sort_impl_01<Result, sizeof...(Next), CompTarget, Next...> stalin_sort_next_wrapper(seq<CompTarget,Next...>) {};
template<class Result>
constexpr stalin_sort_stopper<Result> stalin_sort_next_wrapper(seq<>){};


//seqへinsertする
template<int I, int... Seq>
constexpr seq<Seq...,I> insert(seq<Seq...>) {};

// Target粛清
template<class Result, bool Comp, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01 {
	using next = seq<CompTarget, Rest...>;
	using result = Result;
};

// Target同胞
template<class Result, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01<Result, true, CompTarget, InsertTarget, Rest...> {
	using next = seq<CompTarget, Rest...>;
	using result = decltype(insert<InsertTarget>(Result{}));
};

template<class Result, class Next>
struct stalin_sort_holder_detail : decltype(stalin_sort_next_wrapper<Result>(Next{})) {};
template<class Holder>
struct stalin_sort_holder : stalin_sort_holder_detail<typename Holder::result,typename Holder::next> {};

template<class Result, int A, int B, int ...Rest>
struct stalin_sort_impl_comp_insert : 
	stalin_sort_holder<
		stalin_sort_impl_comp_insert_01<Result, (A <= B), (A <= B) ? B:A, B, Rest...>
	> {};

// result, target, rest_size, rest
// rest_size > 1なら targetとrestのheadを比較
// rest_size = 0ならresult展開して終了
template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01 : stalin_sort_impl_comp_insert<Result, Target, Rest...> {};

template<class Result, int Target, int ...Rest>
struct stalin_sort_impl_01<Result, 0u, Target, Rest...> {
	using result = Result;
};

template<int Target, int...Rest>
struct stalin_sort : stalin_sort_impl_01<seq<Target>, sizeof...(Rest), Target, Rest...> {};

// printer
template<int Head, int ...Tail>
void print_impl() {
	auto& out = std::cout;
	out << Head;
	using expander = int[];
	(void)expander{0, (void(out << ',' << Tail), 0)...};
	out << std::endl;
}


template<int ...Seq>
void print(seq<Seq...>) {
	print_impl<Seq...>();
}



int main() {
	print(typename stalin_sort<0>::result{}); // => 0
	print(typename stalin_sort<2,3>::result{});
	print(typename stalin_sort<2,1,3>::result{}); // => 2,3
	print(typename stalin_sort<1,2,3,4,5>::result{}); // => 1,2,3,4,5
	print(typename stalin_sort<2,1,3,3,2,5,6>::result{}); // => 2,3,3,5,6
	return 0;
}
```

# 解説っぽいもの
### stalin_sort（エントリ関数）
```cpp
template<int Target, int...Rest>
struct stalin_sort : stalin_sort_impl_01<seq<Target>, sizeof...(Rest), Target, Rest...> {};
```
まず、ここで入力された数列に対して**Target**と**Rest**に分解し、先頭の数値を`seq<Target>`へ保持します。`sizeof...(Rest)`によって残りの数列の長さを取得しています。

### stalin_sort_impl_01
```cpp
// result, target, rest_size, rest
// rest_size > 1なら targetとrestのheadを比較
// rest_size = 0ならresult展開して終了
template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01 : stalin_sort_impl_comp_insert<Result, Target, Rest...> {};
 
template<class Result, int Target, int ...Rest>
struct stalin_sort_impl_01<Result, 0u, Target, Rest...> {
	using result = Result;
};
```
`stalin_sort_impl_01`は`reduce`と同じような仕組みで**result**にデータを蓄積していく手法を取っています。また、ここで**Rest**の長さが0の場合に**Result**を返しています。

### 比較と粛清
```cpp
// Target粛清
template<class Result, bool Comp, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01 {
	using next = seq<CompTarget, Rest...>;
	using result = Result;
};
 
// Target同胞
template<class Result, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01<Result, true, CompTarget, InsertTarget, Rest...> {
	using next = seq<CompTarget, Rest...>;
	using result = decltype(insert<InsertTarget>(Result{}));
};

template<class Result, class Next>
struct stalin_sort_holder_detail : decltype(stalin_sort_next_wrapper<Result>(Next{})) {};
template<class Holder>
struct stalin_sort_holder : stalin_sort_holder_detail<typename Holder::result,typename Holder::next> {};

template<class Result, int A, int B, int ...Rest>
struct stalin_sort_impl_comp_insert : 
	stalin_sort_holder<
		stalin_sort_impl_comp_insert_01<Result, (A <= B), (A <= B) ? B:A, B, Rest...>
	> {};
 ```
比較関数の本体です。**(A <= B) ? B : A**がキモで、比較対象の更新をここで行なっています。
`stalin_sort_impl_comp_insert_01`で**(A <= B)**による場合分けを行い、粛清したりしなかったりしています。
その結果を`stalin_sort_holder`と`stalin_sort_holder_detail`で取り出して`stalin_sort_next_wrapper`に渡します。
`stalin_sort_next_wrapper`はseq型になっている**Next**を展開し、**CompTarget**と**Next...**のパラメーターパックを取り出すためのトリックです。この中で`stalin_sort_impl_01`が呼び出されることによって再帰的に計算を実行できています。


### Seqを展開して標準出力に表示する
```cpp
// printer
template<int Head, int ...Tail>
void print_impl() {
	auto& out = std::cout;
	out << Head;
	using expander = int[];
	(void)expander{0, (void(out << ',' << Tail), 0)...};
	out << std::endl;
}
 
 
template<int ...Seq>
void print(seq<Seq...>) {
	print_impl<Seq...>();
}
```
seq型を展開してprintする為のイディオムです。`int[]`の直接初期化構文内でパラメーター展開が利用できる事を使用して出力文を書き、コンマ演算子によって0に評価した後、`(void)`で何もなかったことにしています。

### 結果
```cpp
int main() {
	print(typename stalin_sort<0>::result{}); // => 0
	print(typename stalin_sort<2,3>::result{});
	print(typename stalin_sort<2,1,3>::result{}); // => 2,3
	print(typename stalin_sort<1,2,3,4,5>::result{}); // => 1,2,3,4,5
	print(typename stalin_sort<2,1,3,3,2,5,6>::result{}); // => 2,3,3,5,6
	return 0;
}
```
以上を用いることで無事$O(1)$でスターリンソートを実装することができました。

めでたしめでたし:tada:


# Online Demo
https://shar.es/aXXH86

# PR
折角なのでPR出しておきました。レギュレーション違反だから通るかどうか心配だな:confounded:
https://github.com/gustavo-depaula/stalin-sort/pull/35

> 二度とやりたくない

# 追記1: 無事Mergeされました
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/137384/cc73fc06-5d18-6bc1-6870-84a78889d2da.png)
や　っ　た　ぜ

# 追記2: 闇の同胞
* [モダンな闇の力でスターリンソート！](https://qiita.com/alphya/items/9256dec2632aff07440d)

  闇の同胞がC++17でよりスマートに書いてくださいました！（PRを出すのです……）