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 InsertionSort<T>(T[] arr, Int32 start, Int32 end, Comparison<T> comparison)
    {
        Int32 i, j;
        for (i = start + 1; i <= end; i++)
        {
            T tmp = arr[i];
            for (j = i; j > 0 && comparison(arr[j - 1], tmp) > 0; j--)
            {
                arr[j] = arr[j - 1];
            }
            arr[j] = tmp;
        }
    }

    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 QuickSortWithInsertionSort<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)
        {
            InsertionSort(arr, left, pr, comparison);
        }
        else if (left < pr)
        {
            QuickSortWithInsertionSort(arr, left, pr, comparison);
        }

        if (right - pl <= MinimumDividedArraySize)
        {
            InsertionSort(arr, pl, right, comparison);
        }
        else if (pl < right)
        {
            QuickSortWithInsertionSort(arr, pl, right, comparison);
        }
    }
    public static void QuickSortWithInsertionSort<T>(T[] arr, Comparison<T> comparison) where T : IComparable<T>
    {
        QuickSortWithInsertionSort(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;
        }

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

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