イントロソートを安定ソートとして習作(C#)

C#で安定ソートを行うときはLinqのOrderBy()が一般的だが、OrderByはクイックソートなのでワースト計算量がO(N^2)になってしまう。ここでは、これを回避したソートを習作してみる。

ちなみにC++のstable_sort()だと、安定マージソートをつかってこの問題を回避している。配列を再帰的に分割していき、長さが閾値(15)未満になったら挿入ソートに切り替えるようだ。
https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l03409

これをそのまま移植してもOKなのだが、それでは面白くないので、ここではArray.Sort()のイントロソートを強引に安定化することにする。イントロソートは最初はクイックソートを行い、再帰のレベルがある値を超えたらヒープソートに切り替えるといもので、高速なクイックソートの利点を利用しつつ最悪ケースを回避するアルゴリズムだ。基本的にはこの２つのソートを安定版に作り替えればよい。

以下のMS実装を参考にした。

イントロソート（Array.Sort())
https://referencesource.microsoft.com/#mscorlib/system/array.cs,2a2126edd9ca7eb4
クイックソート（Linq）
https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

static public void StableSort<T>(List<T> list) where T : IComparable
{
    int[] map = new int[list.Count()];
    for (int i = 0; i < list.Count(); i++) map[i] = i;
    StableSort(list, map, 0, list.Count() - 1, (int)Math.Floor(Math.Log(list.Count(), 2)) * 2);

    var tmp = list.ToArray();
    for (int i = 0; i < list.Count(); i++)
    {
        list[i] = tmp[map[i]];
    }
}

static void StableSort<T>(List<T> list, int[] map, int left, int right, int depthLimit) where T : IComparable
{
    if (left >= right) return;

    //stable heap sort
    if (depthLimit == 0)
    {
        StableSort_HeapSort(list, map, left, right);
        return;
    }

    //stable quick sort
    do
    {
        int i = left;
        int j = right;
        int x = map[i + ((j - i) >> 1)];
        do
        {
            while (i < list.Count() && CompareKeys(list, x, map[i]) > 0) i++;
            while (j >= 0 && CompareKeys(list, x, map[j]) < 0) j--;
            if (i > j) break;
            if (i < j)
            {
                int temp = map[i];
                map[i] = map[j];
                map[j] = temp;
            }
            i++;
            j--;
        } while (i <= j);
        if (j - left <= right - i)
        {
            if (left < j) StableSort(list, map, left, j, depthLimit - 1);
            left = i;
        }
        else
        {
            if (i < right) StableSort(list, map, i, right, depthLimit - 1);
            right = j;
        }
    } while (left < right);
}

static void StableSort_HeapSort<T>(List<T> list, int[] map, int lo, int hi) where T : IComparable
{
    int n = hi - lo + 1;
    for (int i = n / 2; i >= 1; i = i - 1)
    {
        StableSort_HeapSort_DownHeap(list, map, i, n, lo);
    }
    for (int i = n; i > 1; i = i - 1)
    {
        Swap(map, lo, lo + i - 1);
        StableSort_HeapSort_DownHeap(list, map, 1, i - 1, lo);
    }
}

static void StableSort_HeapSort_DownHeap<T>(List<T> list, int[] map, int i, int n, int lo) where T : IComparable
{
    int d = map[lo + i - 1];
    int child;
    while (i <= n / 2)
    {
        child = 2 * i;
        if (child < n && CompareKeys(list, map[lo + child - 1], map[lo + child]) < 0)
        {
            child++;
        }
        if (!(CompareKeys(list, d, map[lo + child - 1]) < 0))
            break;
        map[lo + i - 1] = map[lo + child - 1];
        i = child;
    }
    map[lo + i - 1] = d;
}

static void Swap(int[] map, int i, int j)
{
    var tmp = map[i];
    map[i] = map[j];
    map[j] = tmp;
}

static int CompareKeys<T>(List<T> list, int index1, int index2) where T : IComparable
{
    var c = list[index1].CompareTo(list[index2]);
    if (c == 0)
    {
        return index1 - index2;
    }
    return c;
}

当然、ほとんどの場合でOrderByのほうが少し速い。ワーストケースではこちらのほうが大幅に良いパフォーマンスが出るはず・・・だがうまくテストケースを作れなかった。