スターリンソートを改善(ちゃんとソートできる)

六角レンチです(唐突)
前回、色々な[ソートアルゴリズム](https://qiita.com/iodine53/items/504d93977677c5b8ebf5)を実装しました。
公開してから反応たくさんもらえてうれしいです。
# ところで
スターリンソートというのをご存知でしょうか？
自分は兄に`O(n)`のソートアルゴリズムとして教えられて知りました

https://qiita.com/tttol/items/c9e5c74be3366df65bce

この記事にスターリンソートの事が書いてあります。

仕組みとしては
- ソート対象のリストをどんどん見ていく
- もし、データがソートできていない(今の要素と比べて右の要素の方が小さい)時、そのデータを**粛清**し、なかったことにする
- 最後まで見たら返す。
- なんとソートできている！

...といった感じ。

とりあえず、文字だけだと仕組みがわかりずらいのでpythonで書いてみます(結局文字じゃん)
# 普通のスターリンソート
```py
def stalinsort(target:list):
    notsyukusei = [target[0]]
    siberia = []
    for i in target[1:]:
        if i < notsyukusei[-1]:
            # シベリア送り
            siberia.append(i)
        else:
            # 粛清回避
            notsyukusei.append(i)
    return notsyukusei
```
まずは試運転してみましょう
ソートするリストを`[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]`として入れてみます。
```
[1, 8, 9]
```
なんということでしょう
要素の数が3個になってしまいました。

要素が減ってしまうのはソートとして嫌ですね

...ところで、シベリアはどうなっているのでしょうか？
# シベリアを確認してみる
少し改造して、シベリアのリストも返すようにします。
(具体的には、`return notsyukusei`を`return notsyukusei, siberia`に)
もう一度`[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]`を入れてみます...
```
([1, 8, 9], [6, 1, 1, 3, 7, 1, 8])
```
右がシベリア送りされた数字たちです。
<br><br><br></br></br></br>

...これ再帰的にスターリンソートすれば、それぞれソートできるのでは？
# シベリア送り祭り
要はシベリア送りしたものをもう一度招集し、またシベリア送りしてまた招集しなおし...ということ。
こんな感じ
```py
def stalinsort(target:list):
    if len(target) <= 1:
        return target
    else:
        notsyukusei = [target[0]]
        siberia = []
        for i in target[1:]:
            if i < notsyukusei[-1]:
                # シベリア送り
                siberia.append(i)
            else:
                # 粛清回避
                notsyukusei.append(i)
        return notsyukusei, stalinsort(siberia)
```
もう一度`[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]`を入れてみます
実行してみると...
```
([1, 8, 9], ([6, 7, 8], ([1, 1, 3], [1])))
```
なんか括弧だらけで気持ち悪いですが、とりあえずそれぞれソートできています。

ここで、よく見てみると括弧にはそれぞれ二つの要素が存在しています
二つの要素をどんどん合成していけたらソートできそうです。
<br></br>
...**合成(マージ)**？
# スターリン・マージソート
ということで、今日の主役である`スターリン・マージソート`です。
（いい名前思いつかなかった）

簡単に`マージソート`の動きを説明すると
- ソート対象のリストを分割する
- ソート済みのリストを合成していく

この二つで動いています
ここで、ソート対象のリストを分割する際`マージソート`では二分割していますが、この`スターリンソート`を使っても分割できそうです
(マージしてるからこれただのマージソートだろっていうのはなし)

ということで作りました。
```py
def stalin_mergesort(target:list):
    # スターリン・マージソート
    def _merge(rlist:list, llist:list) -> list:
        returnlist = []
        rindex = 0
        lindex = 0
        while rindex != len(rlist) and lindex != len(llist):
            if rlist[rindex] >= llist[lindex]:
                returnlist.append(llist[lindex])
                lindex += 1
            else:
                returnlist.append(rlist[rindex])
                rindex += 1
        returnlist.extend(rlist[rindex:])
        returnlist.extend(llist[lindex:])
        return returnlist

    if len(target) <= 1:
        return target
    else:
        notsyukusei = [target[0]]
        siberia = []
        for i in target[1:]:
            if i < notsyukusei[-1]:
                # シベリア送り
                siberia.append(i)
            else:
                # 粛清回避
                notsyukusei.append(i)
        return _merge(notsyukusei, stalin_mergesort(siberia))
```
`_merge`関数が`マージソート`の**合成**の部分。
下の`if-else`文が先ほどの再帰的な`スターリンソート`です。

<details><summary>どんな感じで動くのか気になる人向け</summary>

```py
def stalin_mergesort(target:list):
    # スターリン・マージソート
    def _merge(rlist:list, llist:list) -> list:
        returnlist = []
        rindex = 0
        lindex = 0
        while rindex != len(rlist) and lindex != len(llist):
            if rlist[rindex] >= llist[lindex]:
                returnlist.append(llist[lindex])
                lindex += 1
            else:
                returnlist.append(rlist[rindex])
                rindex += 1
        returnlist.extend(rlist[rindex:])
        returnlist.extend(llist[lindex:])
        print(returnlist)
        return returnlist

    if len(target) <= 1:
        return target
    else:
        notsyukusei = [target[0]]
        siberia = []
        for i in target[1:]:
            if i < notsyukusei[-1]:
                # シベリア送り
                siberia.append(i)
            else:
                # 粛清回避
                notsyukusei.append(i)
        print(notsyukusei, siberia)
        return _merge(notsyukusei, stalin_mergesort(siberia))
```
printを付けてわかりやすくしました

`[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]`を引数として実行すると、出力は下になる
```
[1, 8, 9] [6, 1, 1, 3, 7, 1, 8]
[6, 7, 8] [1, 1, 3, 1]
[1, 1, 3] [1]
[1, 1, 1, 3]
[1, 1, 1, 3, 6, 7, 8]
[1, 1, 1, 1, 3, 6, 7, 8, 8, 9]
```
前半3個が`スターリンソート`、後半3個が`マージソート`の合成(マージ)。

前半3個を順を追って見ていくと
- `[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]`をスターリンソートし、`[1, 8, 9]`と`[6, 1, 1, 3, 7, 1, 8]`を分離
- `[6, 1, 1, 3, 7, 1, 8]`をスターリンソートし、`[6, 7, 8]`と`[1, 1, 3, 1]`を分離
- `[1, 1, 3, 1]`をスターリンソートし、`[1, 1, 3]`と`[1]`を分離
- [1]はリストの長さが1以下なので、そのまま返す(ソート済み)

後半三個も同様に見ていくと
- `[1]`と`[1, 1, 3]`を合成し、`[1, 1, 1, 3]`を作成
- `[1, 1, 1, 3]`と`[6, 7, 8]`を合成し、`[1, 1, 1, 3, 6, 7, 8]`を作成
- `[1, 1, 1, 3, 6, 7, 8]`と`[1, 8, 9]`を合成し、`[1, 1, 1, 1, 3, 6, 7, 8, 8, 9]`を作成
- ソート完了

といった感じに動く
</details>

# 試運転
もう一度、`[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]`を入れてみます...
```
[1, 1, 1, 1, 3, 6, 7, 8, 8, 9]
```
ちゃんとソートできてますし、要素の数が減っていません
# 速度測定
ソートできるならやることは一つ。速度を測ります
## 環境
- CPU Core i7 4770
- OS Windows 10
- Python 3.9.6

## 測定方法
[前回の記事](https://qiita.com/iodine53/items/504d93977677c5b8ebf5#計測)と同じく、
ランダムなリストの生成には下の関数を使います
```py
def random_list_gen(num:int, maxnum:int = 9) -> list:
    import random
    return [random.randint(0, maxnum) for _ in range(num)]
```
引数として、要素の数、上限値を受け取ってランダムな数字のリストを返す感じの関数です
maxnumを10000000に固定して要素の数を変化させながら測定します

https://github.com/35enidoi/honi-programs/tree/main/honis/sorts

また、このリポジトリにスターリン・マージソートとこの速度測定で使ったプログラムが置いてあります
`speedtest.py`の一番下の`target = profiles[1]`みたいなところを`target = profiles[7]`に変更すれば同じ測定ができるはず

## 結果
![stalin_ossssso.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3594202/45109a30-2d42-ba48-6070-13412624a7f0.png)
縦軸は一回のソートにかかった時間、横軸は要素の数です。
上に行くほど遅くなり、下に行くほど速いです。

なので、**遅いです**。
ソートはできるようになりましたが遅いので実用性はないです

なんで遅いのかは知りません(そこまで調べるのはめんどくさそう)

<details><summary>ちなみに</summary>

![stalin_margesortoooo.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3594202/46581889-0e55-81e9-edb3-3a9381f6ff20.png)

さすがに選択ソートには勝てます
</details>

<br></br>

# おまけ
haskellで書いてみました
ただreverse使ってるのであまりよくないかも
```hs
merge :: [Int] -> [Int] -> [Int]
merge n [] = n
merge [] n = n
merge (x:xs) (y:ys)
    | x < y     = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

stalin :: [Int] -> [Int] -> [Int] -> ([Int], [Int])
stalin [] y siberia = (y, siberia)
stalin (x:xs) [] siberia = stalin xs [x] siberia
stalin (x:xs) (y:ys) siberia
    | x < y     = stalin xs (y:ys) (x:siberia)
    | otherwise = stalin xs (x:y:ys) siberia

stalinmergesort :: [Int] -> [Int]
stalinmergesort [] = []
stalinmergesort [x] = [x]
stalinmergesort x = merge a b
    where
        c = stalin x [] []
        a = reverse $ fst c
        b = stalinmergesort $ reverse $ snd c
```