#はじめに
夏ぼっちカレンダー（仮）の18日目の記事です。
記事の中に間違いなどあれば指摘していただけると幸いです。

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

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)」です。
他に、Sort()やSort(IComparer)があります。

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

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

① 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にするとクイックソートになりました。

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

#参考
C#の配列やListをソートする (List.Sort)
List.Sort Method
C#の安定ソートを検討
 ノームソート
 【Unity】ソートアルゴリズム12種を可視化してみた
 Sortメソッドの並び替え順序
 ヒープソート
 イントロソート
 挿入ソート
 C# デリゲートについて
 Comparison Delegate