List.Sort((a,b)=>(a-b))について

#はじめに
[夏ぼっちカレンダー（仮）](https://qiita.com/pirorirori_n712/items/4dc66870ccd3cc540f68)の18日目の記事です。
記事の中に間違いなどあれば指摘していただけると幸いです。

#List.Sort((a,b)=>(a-b))がよく分からない
要素数5のリストの
List.Sort((a,b)=>(a-b))の中身を以下のコードで出力してみます。

```csharp
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var list = new List<int>();
        for (int i=5; 1 <= i; --i)
        {
            list.Add(i);
        }

        Console.WriteLine("ソート前");
        Console.WriteLine();

        foreach (var i in list)
        {
            Console.Write($"{i} ");
        }
        Console.WriteLine();

        Console.WriteLine("ソート");
        Console.WriteLine();

        list.Sort((a, b) => {
            Console.Write($"a:{a} ");
            Console.Write($"b:{b} ");
            Console.WriteLine($"a-b:{a-b}");
            return a - b;
        });

        Console.WriteLine();
        Console.WriteLine("ソート後");
        Console.WriteLine();

        foreach (var l in list)
        {
            Console.Write($"{l} ");
        }
    }
}
```

すると以下のように出力されます

```
ソート前

5 4 3 2 1 

ソート

a:4 b:5 a-b:-1
a:3 b:5 a-b:-2
a:3 b:4 a-b:-1
a:2 b:5 a-b:-3
a:2 b:4 a-b:-2
a:2 b:3 a-b:-1
a:1 b:5 a-b:-4
a:1 b:4 a-b:-3
a:1 b:3 a-b:-2
a:1 b:2 a-b:-1

ソート後

1 2 3 4 5 
```

##よく分からないところ
①それぞれのaとbの値の決め方
②ループの回る回数（処理の回数）
③returnされた値の利用方法

#Sortについて
まず、順番が前後しますが「③returnされた値の利用方法」についてです。

Sortにはいくつか種類があり、
ここで使用されている種類は「Sort(Comparison<T>)」です。
他に、Sort()やSort(IComparer<T>)があります。

Sort(Comparison<T>)はComparison<T>デリゲートから返された値が
負の場合に要素の位置を交換します。

つまり、
上の例では以下のことが起こっています。

① 5 4 3 2 1の配列が存在
② 4と5が比較され、-1が返される
③ 負の値が返されたので4と5の順番を逆にする
④ 4 5 3 2 1の配列になる
⑤ 3と5が比較され、-2が返される
⑥ 負の値が返されたので3と5の順番を逆にする
⑦ 4 3 5 2 1の配列になる
…

ここから、
「③returnされた値の利用方法」は
負の時に要素の順番を入れ替えることだということが分かります。


#並び替えるアルゴリズムの選択
次に
「①それぞれのaとbの値の決め方」と「②ループの回る回数（処理の回数）」
についてです。

要素が16未満の際は「挿入ソート」
それ以外は（たぶん）イントロソート（クイックソート＋ヒープソート）
の使用になるようです。

上の要素数は5だったので
挿入ソートが行われていました。

そのため、
「①それぞれのaとbの値の決め方」と「②ループの回る回数（処理の回数）」も
挿入ソートの方法に沿ったものになっていました。


要素数を20にするとクイックソートになりました。

```csharp
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var list = new List<int>();
        for (int i = 20; 1 <= i; --i)
        {
            list.Add(i);
        }

        Console.WriteLine("ソート前");
        Console.WriteLine();
        foreach (var i in list)
        {
            Console.Write($"{i} ");
        }
        Console.WriteLine();

        Console.WriteLine("ソート");
        Console.WriteLine();

        list.Sort((a, b) => {
            Console.Write($"a:{a} ");
            Console.Write($"b:{b} ");
            Console.WriteLine($"a-b:{a-b}");
            return a - b;
        });

        Console.WriteLine();
        Console.WriteLine("ソート後");
        Console.WriteLine();

        foreach (var l in list)
        {
            Console.Write($"{l} ");
        }
    }
}

```
以下のように出力されます

```
ソート前

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 

ソート

a:20 b:11 a-b:9
a:11 b:1 a-b:10
a:20 b:11 a-b:9
a:19 b:11 a-b:8
a:11 b:3 a-b:8
a:18 b:11 a-b:7
a:11 b:4 a-b:7
a:17 b:11 a-b:6
a:11 b:5 a-b:6
a:16 b:11 a-b:5
a:11 b:6 a-b:5
a:15 b:11 a-b:4
a:11 b:7 a-b:4
a:14 b:11 a-b:3
a:11 b:8 a-b:3
a:13 b:11 a-b:2
a:11 b:9 a-b:2
a:12 b:11 a-b:1
a:11 b:10 a-b:1
a:2 b:11 a-b:-9
a:12 b:11 a-b:1
a:11 b:2 a-b:9
a:14 b:13 a-b:1
a:15 b:14 a-b:1
a:16 b:15 a-b:1
a:17 b:16 a-b:1
a:18 b:17 a-b:1
a:19 b:18 a-b:1
a:12 b:19 a-b:-7
a:12 b:18 a-b:-6
a:12 b:17 a-b:-5
a:12 b:16 a-b:-4
a:12 b:15 a-b:-3
a:12 b:14 a-b:-2
a:12 b:13 a-b:-1
a:20 b:19 a-b:1
a:3 b:1 a-b:2
a:4 b:3 a-b:1
a:5 b:4 a-b:1
a:6 b:5 a-b:1
a:7 b:6 a-b:1
a:8 b:7 a-b:1
a:9 b:8 a-b:1
a:10 b:9 a-b:1
a:2 b:10 a-b:-8
a:2 b:9 a-b:-7
a:2 b:8 a-b:-6
a:2 b:7 a-b:-5
a:2 b:6 a-b:-4
a:2 b:5 a-b:-3
a:2 b:4 a-b:-2
a:2 b:3 a-b:-1
a:2 b:1 a-b:1

ソート後

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
```

ここから、
「①それぞれのaとbの値の決め方」と「②ループの回る回数」は、
ソートする際に使用するアルゴリズムによることが分かりました。

#まとめ
・Sort(Comparison<T>)はComparison<T>デリゲートから返された値が、負の場合に要素の位置を交換する
・デリゲートの引数の値の決め方と、処理の回数はアルゴリズムによる

#参考
[C#の配列やListをソートする (List.Sort)](https://araramistudio.jimdo.com/2018/08/27/c-%E3%81%AE%E9%85%8D%E5%88%97%E3%82%84list%E3%82%92%E3%82%BD%E3%83%BC%E3%83%88%E3%81%99%E3%82%8B/)
[List<T>.Sort Method](https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1.sort?view=netframework-4.8)
[C#の安定ソートを検討](https://blog.wizaman.net/archives/1091)
[ノームソート](https://ja.wikipedia.org/wiki/%E3%83%8E%E3%83%BC%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88)
[【Unity】ソートアルゴリズム12種を可視化してみた](https://qiita.com/r-ngtm/items/f4fa55c77459f63a5228)
[Sortメソッドの並び替え順序](https://teratail.com/questions/98273)
[ヒープソート](http://www.th.cs.meiji.ac.jp/assets/researches/2005/omoto/heapsort.html)
[イントロソート](http://wwwa.pikara.ne.jp/okojisan/sort/introsort.html)
[挿入ソート](https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88)
[C# デリゲートについて](https://qiita.com/ysn551/items/71fe3f332ea9a3114d36)
[Comparison<T> Delegate](https://docs.microsoft.com/ja-jp/dotnet/api/system.comparison-1?redirectedfrom=MSDN&view=netframework-4.8)