using System.Collections.Generic;

namespace Algorithms.Sorters.Comparison;

/// <summary>
///     Sorts arrays using quicksort (selecting median of three as a pivot).
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public sealed class MedianOfThreeQuickSorter<T> : QuickSorter<T>
{
    protected override T SelectPivot(T[] array, IComparer<T> comparer, int left, int right)
    {
        var leftPoint = array[left];
        var middlePoint = array[left + (right - left) / 2];
        var rightPoint = array[right];

        return FindMedian(comparer, leftPoint, middlePoint, rightPoint);
    }

    private static T FindMedian(IComparer<T> comparer, T a, T b, T c)
    {
        if (comparer.Compare(a, b) <= 0)
        {
            // a <= b <= c
            if (comparer.Compare(b, c) <= 0)
            {
                return b;
            }

            // a <= c < b
            if (comparer.Compare(a, c) <= 0)
            {
                return c;
            }

            // c < a <= b
            return a;
        }

        // a > b >= c
        if (comparer.Compare(b, c) >= 0)
        {
            return b;
        }

        // a >= c > b
        if (comparer.Compare(a, c) >= 0)
        {
            return c;
        }

        // c > a > b
        return a;
    }
}