C# クイックソートと二分挿入ソートの組み合わせによるソート

クイックソートの分割配列が一定の要素数になったら挿入ソートに切り替えることにより、クイックソートを高速化する手法があるが、ここでは挿入ソートではなく二分挿入ソートで実装した。

using System;
using System.Collections.Generic;

class Program
{
    private static void Swap<T>(ref T a, ref T b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }

    public static void BinaryInsertionSort<T>(T[] arr, Int32 start, Int32 end, Comparison<T> comparison)
    {
        for (Int32 i = start + 1; i <= end; i++)
        {
            T n = arr[i];
            Int32 left = start;
            Int32 right = i;
            while (left < right)
            {
                Int32 m = (left + right) / 2;
                if (comparison(arr[m], arr[i]) <= 0)
                {
                    left = m + 1;
                }
                else
                {
                    right = m;
                }
            }
            Int32 j;
            for (j = i; j > right; j--)
            {
                arr[j] = arr[j - 1];
            }
            arr[j] = n;
        }
    }

    private static T MedianOfThree<T>(T a, T b, T c) where T : IComparable<T>
    {
        if (a.CompareTo(b) >= 0)
        {
            if (a.CompareTo(c) <= 0)
            {
                return a;
            }
        }

        if (b.CompareTo(c) >= 0)
        {
            if (b.CompareTo(a) <= 0)
            {
                return b;
            }
        }

        if (c.CompareTo(a) >= 0)
        {
            if (c.CompareTo(b) <= 0)
            {
                return c;
            }
        }

        return b;
    }
    private static void _QuickSortWithBinaryInsertionSort<T>(T[] arr, Int32 left, Int32 right, Comparison<T> comparison) where T : IComparable<T>
    {
        const Int32 MinimumDividedArraySize = 20;
        Int32 pl = left;
        Int32 pr = right;
        T pivot = MedianOfThree(arr[pl], arr[(pl + pr) / 2], arr[pr]);
        do
        {
            while (comparison(arr[pl], pivot) < 0) pl++;
            while (comparison(arr[pr], pivot) > 0) pr--;
            if (pl <= pr)
            {
                Swap(ref arr[pl], ref arr[pr]);
                pl++;
                pr--;
            }
        } while (pl <= pr);

        if (pr - left <= MinimumDividedArraySize)
        {
            BinaryInsertionSort(arr, left, pr, comparison);
        }
        else if (left < pr)
        {
            _QuickSortWithBinaryInsertionSort(arr, left, pr, comparison);
        }

        if (right - pl <= MinimumDividedArraySize)
        {
            BinaryInsertionSort(arr, pl, right, comparison);
        }
        else if (pl < right)
        {
            _QuickSortWithBinaryInsertionSort(arr, pl, right, comparison);
        }
    }
    public static void QuickSortWithBinaryInsertionSort<T>(T[] arr, Comparison<T> comparison) where T : IComparable<T>
    {
        _QuickSortWithBinaryInsertionSort(arr, 0, arr.Length - 1, comparison);
    }

    public static void Main()
    {
        const Int32 N = 100;
        Int32[] a = new Int32[N];
        Random rand = new Random();
        for (Int32 i = 0; i < a.Length; i++)
        {
            a[i] = rand.Next() % a.Length;
        }

        QuickSortWithBinaryInsertionSort(a, delegate(Int32 x, Int32 y) { return x.CompareTo(y); });

        Array.ForEach(a, delegate(Int32 n) { Console.WriteLine(n); });
    }
}