QuickSorter.cs

using System.Collections.Generic;

namespace Algorithms.Sorters.Comparison
{
    /// <summary>
    ///     Sorts arrays using quicksort.
    /// </summary>
    /// <typeparam name="T">Type of array element.</typeparam>
    public abstract class QuickSorter<T> : IComparisonSorter<T>
    {
        /// <summary>
        ///     Sorts array using Hoare partition scheme,
        ///     internal, in-place,
        ///     time complexity average: O(n log(n)),
        ///     time complexity worst: O(n^2),
        ///     space complexity: O(log(n)),
        ///     where n - array length.
        /// </summary>
        /// <param name="array">Array to sort.</param>
        /// <param name="comparer">Compares elements.</param>
        public void Sort(T[] array, IComparer<T> comparer) => Sort(array, comparer, 0, array.Length - 1);

        protected abstract T SelectPivot(T[] array, IComparer<T> comparer, int left, int right);

        private void Sort(T[] array, IComparer<T> comparer, int left, int right)
        {
            if (left >= right)
            {
                return;
            }

            var p = Partition(array, comparer, left, right);
            Sort(array, comparer, left, p);
            Sort(array, comparer, p + 1, right);
        }

        private int Partition(T[] array, IComparer<T> comparer, int left, int right)
        {
            var pivot = SelectPivot(array, comparer, left, right);
            var nleft = left;
            var nright = right;
            while (true)
            {
                while (comparer.Compare(array[nleft], pivot) < 0)
                {
                    nleft++;
                }

                while (comparer.Compare(array[nright], pivot) > 0)
                {
                    nright--;
                }

                if (nleft >= nright)
                {
                    return nright;
                }

                var t = array[nleft];
                array[nleft] = array[nright];
                array[nright] = t;

                nleft++;
                nright--;
            }
        }
    }
}