スターリンソートをLINQと拡張メソッドで実装

#概要

[これ](https://qiita.com/Tatsuki-I/items/380d6bd06515b872b2b2
)を見て何となく自分もスターリンソートを書いてみました。

~~また、[公式](https://github.com/gustavo-depaula/stalin-sort/blob/master/c%23/stalin-sort/Program.cs)でC#のコードが掲載されていましたが、拡張メソッドやLINQ、ジェネリックなどが全然使われていない！
これは**C#信者として見過ごす訳にはいきません。**(過激派)~~
(2019/08/04追記)
他の有志のプルリクによって、`IEnumerable<T>`を返す実装になりました。
ただ、現時点のソースコードにおいても下記のような実装はされていません。

- 拡張メソッドで呼べるようにする
- 昇順降順を決める
- 比較方法をカスタマイズする
- ソート済みのコレクションを更にソートする

ということで、上記の機能を実装してみます。
`C# 8.0`で動作を確認しています。コンパイルが通らない場合は`using変数`辺りを修正すれば動作すると思います。

# 拡張クラス

```C#
using System;
using System.Linq;
using System.Collections.Generic;

namespace StalinSort
{
    static class StalinSortExtension
    {
        public static IOrderedEnumerable<TSource> StalinSortBy<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector)
        {
            return source
                .StalinSort(keySelector, null, false)
                .OrderBy(keySelector);
        }

        public static IOrderedEnumerable<TSource> StalinSortBy<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            IComparer<TKey> comparer)
        {
            return source
                .StalinSort(keySelector, comparer, false)
                .OrderBy(keySelector, comparer);
        }

        public static IOrderedEnumerable<TSource> StalinSortByDescending<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector)
        {
            return source
                .StalinSort(keySelector, null, true)
                .OrderByDescending(keySelector);
        }

        public static IOrderedEnumerable<TSource> StalinSortByDescending<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            IComparer<TKey> comparer)
        {
            return source
                .StalinSort(keySelector, comparer, true)
                .OrderByDescending(keySelector, comparer);
        }

        private static IEnumerable<TSource> StalinSort<TSource, TKey>(
            this IEnumerable<TSource> source,
            Func<TSource, TKey> keySelector,
            IComparer<TKey> comparer,
            bool descending)
        {
            using var iterator = source.GetEnumerator();
            if (iterator.MoveNext())
            {
                var c = comparer ?? Comparer<TKey>.Default;
                TKey last = keySelector(iterator.Current);
                yield return iterator.Current;
                while (iterator.MoveNext())
                {
                    TKey current = keySelector(iterator.Current);
                    bool condition = descending ? c.Compare(last, current) >= 0 : c.Compare(last, current) <= 0;
                    if (condition)
                    {
                        last = current;
                        yield return iterator.Current;
                    }
                }
            }
        }
    }
}
```

#実行サンプル
```C#
using System;
using System.Linq;
using System.Collections.Generic;
using StalinSort;

namespace asobi
{
    public class Program
    {
        public static void Main()
        {
            var list = new List<int>() { 6, 8, 5, 9, 11, 12, 4, 2, 7, 9 };
            foreach (var e in list.StalinSortBy(x => x))
            {
                Console.WriteLine(e);
            }
            /* 
             * output:
             * 6
             * 8
             * 9
             * 11
             * 12
             */

            var fruits = new List<Fruit>(){
                new Fruit{ Name = "オレンジ", Price = 80 },
                new Fruit{ Name = "ピーチ", Price = 150 },
                new Fruit{ Name = "バナナ", Price = 50 },
                new Fruit{ Name = "グレープ", Price = 250 },
                new Fruit{ Name = "ストロベリー", Price = 20 },
                new Fruit{ Name = "ウォーターメロン", Price = 1200 },
                new Fruit{ Name = "メロン", Price = 2000 },
            };
            
            foreach (var e in fruits.StalinSortBy(x => x.Name.Length).ThenByDescending(x => x.Price))
            {
                Console.WriteLine($"Name:{e.Name} Price:{e.Price}");
            }
            /*
             *output:
             *Name:グレープ Price:250
             *Name:オレンジ Price:80
             *Name:ストロベリー Price:20
             *Name:ウォーターメロン Price:1200
             */
        }
    }

    public class Fruit{
        public string Name;
        public int Price;
    }
}

```

#要点
- 現在進行形で最大値の要素(`last`)と要素(`current`)を比較
- `IComparer`を使ってその型(`TKey`)特有の比較ができる
- 見ての通り遅延評価を行っているため、`source`の順序が崩れる心配はない
- 仕組みは[OrderByの内部実装](https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,e449fbc07f49dc52)とある程度は似せているつもり
- `ThenBy`による並び変えをできるようにするため`IOrderedEnumerable<TSource>`を返す(ただ、メソッド内部で`OrderBy`を返したのはかなりズルをしたと思います)

# 余談
公式のリポジトリに無事マージされました。
https://github.com/gustavo-depaula/stalin-sort/tree/master/c%23/stalin-sort-with-extension