using System;

namespace Exercise2
{
    class QuickSort
    {
        public static void Sort<T>(T[] arr)
            where T : IComparable
        {
            SortingAlgorithms.FisherYates(arr);
            Sort(arr, 0, arr.Length - 1);
        }

        private static void Sort<T>(T[] arr, int leftIndex, int rightIndex)
            where T : IComparable
        {
            if (leftIndex >= rightIndex)
                return;

            if (rightIndex - leftIndex < 7)
            {
                SortingAlgorithms.InsertionSort(arr, leftIndex, rightIndex + 1);
                return;
            }

            int leftCounter = leftIndex;
            int rightCounter = rightIndex + 1;
            int sameElementsLeft = leftIndex;
            int sameElementRight = rightIndex + 1;
            T item = arr[leftIndex];

            while (true)
            {
                while (item.CompareTo(arr[++leftCounter]) > 0)
                {
                    if (leftCounter == rightIndex)
                        break;
                }

                while (item.CompareTo(arr[--rightCounter]) < 0)
                {
                    if (rightCounter == leftIndex)
                        break;
                }

                if (leftCounter >= rightCounter)
                    break;

                Swap(ref arr[leftCounter], ref arr[rightCounter]);

                if (item.CompareTo(arr[leftCounter]) == 0)
                    Swap(ref arr[leftCounter], ref arr[++sameElementsLeft]);

                if (item.CompareTo(arr[rightCounter]) == 0)
                    Swap(ref arr[rightCounter], ref arr[--sameElementRight]);
            }

            Swap(ref arr[leftIndex], ref arr[rightCounter]);

            rightCounter--;

            for (int cnt = leftIndex; cnt < sameElementsLeft; cnt++)
            {
                Swap(ref arr[cnt], ref arr[rightCounter]);
                rightCounter--;
            }

            for (int cnt = rightIndex - 1; cnt > sameElementRight; cnt--)
            {
                Swap(ref arr[cnt], ref arr[leftCounter]);
                leftCounter++;
            }

            Sort(arr, leftIndex, rightCounter);
            Sort(arr, leftCounter, rightIndex);
        }

        public static void Swap<T>(ref T first, ref T second)
        {
            T temp = first;
            first = second;
            second = temp;
        }
    }
}