QuickSortDualPivot

QuickSortDualPivot.cs

public class QuickSortDualPivot<T>
{
    private readonly IComparer<T> _comparer;

    public QuickSortDualPivot(IComparer<T> comparer)
    {
        _comparer = comparer;
    }

    public void Sort(T[] input)
    {
        Sort(input, 0, input.Length - 1);
    }

    private void Sort(T[] input, int lowIndex, int highIndex)
    {
        if (highIndex <= lowIndex)
            return;
        T pivot1 = input[lowIndex];
        T pivot2 = input[highIndex];

        if (Less(pivot2, pivot1))
        {
            Exchange(input, lowIndex, highIndex);
            pivot1 = input[lowIndex];
            pivot2 = input[highIndex];
        }

        int i = lowIndex + 1;
        int lt = lowIndex + 1;
        int gt = highIndex - 1;

        while (i <= gt)
        {

            if (Less(input[i], pivot1))
            {
                Exchange(input, i++, lt++);
            }
            else if (Less(pivot2, input[i]))
            {
                Exchange(input, i, gt--);
            }
            else {
                i++;
            }

        }


        Exchange(input, lowIndex, --lt);
        Exchange(input, highIndex, ++gt);

        Sort(input, lowIndex, lt - 1);
        Sort(input, lt + 1, gt - 1);
        Sort(input, gt + 1, highIndex);
    }

    private bool Less(T a, T b)
    {
        return _comparer.Compare(a, b) < 0;
    }

    private static void Exchange(T[] input, int lowIndex, int highIndex)
    {
        var tmp = input[lowIndex];
        input[lowIndex] = input[highIndex];
        input[highIndex] = tmp;
    }
}