using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestMyQuick
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = new int[10000];
            int len = 10000;

            Random random = new Random();

            for (int i = 0; i < len; i++)
            {
                numbers[i] = random.Next(1000000);
            }

            IterativeQuickSort(numbers);
        }

        public static void IterativeQuickSort(IList<int> collection)
        {
            Stack<int> stack = new Stack<int>();

            stack.Push(0);
            stack.Push(collection.Count-1);

            while (stack.Count!=0)
            {
                int right = stack.Pop();
                int left = stack.Pop();

                if (right - left < 1)
                {
                    continue;
                }

                int pivotNext = Partition(collection, left, right);

                stack.Push(pivotNext + 1);
                stack.Push(right);

                stack.Push(left);
                stack.Push(pivotNext);
            }
        }

        static int Partition(IList<int> collection, int left, int right)
        {
            int index = Median(left, right, collection);
            int temp = collection[left];
            int pivot = collection[index];
            collection[index] = temp;
            collection[left] = pivot;

            int i = left + 1;

            for (int j = left + 1; j <= right; j++)
            {
                if (collection[j] < pivot)
                {

                    temp = collection[i];
                    collection[i] = collection[j];
                    collection[j] = temp;
                    i++;
                }
            }

            temp = collection[left];
            collection[left] = collection[i - 1];
            collection[i - 1] = temp;
            return i - 1;
        }

        static int Median(int left, int right, IList<int> collection)
        {
         //   comparasions += (right - left);
            int middle = (right + left) / 2;

            if ((collection[middle] < collection[left] && collection[middle] > collection[right]) ||
                (collection[middle] > collection[left] && collection[middle] < collection[right]))
            {
                return middle;
            }
            else if ((collection[right] < collection[middle] && collection[right] > collection[left]) ||
                (collection[right] > collection[middle] && collection[right] < collection[left]))
            {
                return right;
            }
            else
            {
                return left;
            }
        }
    }
}