🔥
[Unity/C#] LinqのSortは安定ソートではない

2025/05/06に公開
 前提Unity/C#でLinqのSortメソッドを使うと、たまにソート結果が安定でないように見えます。

ネットで調べて安定ソートではないとわかったのですが、手元で実験するとなかなか再現しませんでした。
いろいろ試して、不安定なソートが再現する場合を見つけたので忘備録として残しておきます。

 実験環境Unity 2022.3.12f1
ピュアなc#で実験すべきだと思いますが、Unityで実験しています。

 実験以下のソースコードを任意のGameObjectにアタッチして実行します。
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class SortStabilityTest : MonoBehaviour
{
    public class Item
    {
        public int Key;
        public string Name;

        public override string ToString() => $"Key: {Key}, Name: {Name}";
    }

    void Start()
    {
        var items = new List<Item>();

        for (int i = 0; i < 100; i++)
        {
            var item = new Item
            {
                Key = 0,
                Name = "Item" + i
            };
            items.Add(item);
        }

        // ソート前
        var beforeSortMsg = "=== before sort ===\n";
        foreach (var item in items)
        {
            beforeSortMsg += item.ToString() + "\n";
        }
        Debug.Log(beforeSortMsg);

        // ソート
        items.Sort((a, b) => a.Key.CompareTo(b.Key));

        // ソート後
        var afterSortMsg = "=== after sort ===\n";
        foreach (var item in items)
        {
            afterSortMsg += item.ToString() + "\n";
        }
        Debug.Log(afterSortMsg);
    }
}

 結果
 ソート前のログすべての要素のKeyは0で、NameはItem0, Item1, ...のようになっています。
=== before sort ===
Key: 0, Name: Item0
Key: 0, Name: Item1
Key: 0, Name: Item2
Key: 0, Name: Item3
Key: 0, Name: Item4
Key: 0, Name: Item5

...中略...

Key: 0, Name: Item93
Key: 0, Name: Item94
Key: 0, Name: Item95
Key: 0, Name: Item96
Key: 0, Name: Item97
Key: 0, Name: Item98
Key: 0, Name: Item99

 ソート後のログKeyを用いてソートを行いました。

仮に安定ソートだとすると、すべての要素のKeyが0なので、Nameの順番は変わらないはずです。
ログの冒頭を載せておきます。短いですが、安定ソートになっていないことがわかります。

（安定ならば、Item0, Item1, Item2, ...のようにならぶはず）
=== after sort ===
Key: 0, Name: Item0
Key: 0, Name: Item72
Key: 0, Name: Item71
Key: 0, Name: Item70
Key: 0, Name: Item69
Key: 0, Name: Item68
Key: 0, Name: Item67
Key: 0, Name: Item66
Key: 0, Name: Item65

...略...
一応全ログも載せておきます。
ソート後の全ログ=== after sort ===
Key: 0, Name: Item0
Key: 0, Name: Item72
Key: 0, Name: Item71
Key: 0, Name: Item70
Key: 0, Name: Item69
Key: 0, Name: Item68
Key: 0, Name: Item67
Key: 0, Name: Item66
Key: 0, Name: Item65
Key: 0, Name: Item64
Key: 0, Name: Item63
Key: 0, Name: Item62
Key: 0, Name: Item61
Key: 0, Name: Item60
Key: 0, Name: Item59
Key: 0, Name: Item58
Key: 0, Name: Item57
Key: 0, Name: Item56
Key: 0, Name: Item55
Key: 0, Name: Item54
Key: 0, Name: Item53
Key: 0, Name: Item52
Key: 0, Name: Item73
Key: 0, Name: Item51
Key: 0, Name: Item74
Key: 0, Name: Item76
Key: 0, Name: Item97
Key: 0, Name: Item96
Key: 0, Name: Item95
Key: 0, Name: Item94
Key: 0, Name: Item93
Key: 0, Name: Item92
Key: 0, Name: Item91
Key: 0, Name: Item90
Key: 0, Name: Item89
Key: 0, Name: Item88
Key: 0, Name: Item87
Key: 0, Name: Item86
Key: 0, Name: Item85
Key: 0, Name: Item84
Key: 0, Name: Item83
Key: 0, Name: Item82
Key: 0, Name: Item81
Key: 0, Name: Item80
Key: 0, Name: Item79
Key: 0, Name: Item78
Key: 0, Name: Item77
Key: 0, Name: Item75
Key: 0, Name: Item50
Key: 0, Name: Item49
Key: 0, Name: Item48
Key: 0, Name: Item21
Key: 0, Name: Item20
Key: 0, Name: Item19
Key: 0, Name: Item18
Key: 0, Name: Item17
Key: 0, Name: Item16
Key: 0, Name: Item15
Key: 0, Name: Item14
Key: 0, Name: Item13
Key: 0, Name: Item12
Key: 0, Name: Item11
Key: 0, Name: Item10
Key: 0, Name: Item9
Key: 0, Name: Item8
Key: 0, Name: Item7
Key: 0, Name: Item6
Key: 0, Name: Item5
Key: 0, Name: Item4
Key: 0, Name: Item3
Key: 0, Name: Item2
Key: 0, Name: Item1
Key: 0, Name: Item22
Key: 0, Name: Item23
Key: 0, Name: Item24
Key: 0, Name: Item25
Key: 0, Name: Item47
Key: 0, Name: Item46
Key: 0, Name: Item45
Key: 0, Name: Item44
Key: 0, Name: Item43
Key: 0, Name: Item42
Key: 0, Name: Item41
Key: 0, Name: Item40
Key: 0, Name: Item39
Key: 0, Name: Item38
Key: 0, Name: Item98
Key: 0, Name: Item37
Key: 0, Name: Item35
Key: 0, Name: Item34
Key: 0, Name: Item33
Key: 0, Name: Item32
Key: 0, Name: Item31
Key: 0, Name: Item30
Key: 0, Name: Item29
Key: 0, Name: Item28
Key: 0, Name: Item27
Key: 0, Name: Item26
Key: 0, Name: Item36
Key: 0, Name: Item99

 まとめLinqのSortメソッドを使用したソートが不安定になる例を載せました。
ネットやChatGPTで調べた検証コードを用いても、ソート結果が安定になってしまうことが多く、なかなか不安定な例を再現しませんでした。
いろいろ試してみたところ、リストのサイズが10個などの小さい場合、Sortメソッドを使用しても安定になる（ようにみえる）ことが多いようでした。上の実験でも、リストの要素の数を100個から10個へと変更するとソート結果は安定でした。
ちなみに、OrderByメソッドは安定ソートらしいので、安定ソートが必要な場合はOrderByを使用するのが良さそうです。もちろん、内部のアルゴリズムは実装によるので、自分で実験したりドキュメントや実装を確認することをおすすめします
前提

実験環境

実験

結果

ソート前のログ

ソート後のログ

まとめ

Discussion
