class QuickSort
    {
        private void Swap(ref int i, ref int j)
        {
            int t;
            t = i;
            i = j;
            j = t;
        }
        public void Sort(int[] list, int low, int high)
        {
            if (high <= low)
            {//only one element i array list
                //so it do not need sort
                return;
            }
            else if (high == low + 1)
            {
                if (list[low] > list[high])
                {
                    Swap(ref list[low], ref list[high]);
                    return;
                }
            }
            myQuickSort(list, low, high);
        }
        private void myQuickSort(int[] list, int low, int high)
        {
            if (low < high)
            {
                int pivot = Partition(list, low, high);
                myQuickSort(list, low, pivot - 1);
                myQuickSort(list, pivot + 1, high);
            }
        }
        private int Partition(int[] list, int low, int high)
        {
            int pivot;
            pivot = list[low];
            while (low < high)
            {
                while(low <high&&list[high]>=pivot)
                {
                    high--;
                }
                if(low!=high)
                {
                    Swap(ref list[low], ref list[high]);
                    low++;
                }
                while(low<high&&list[low]<=pivot)
                {
                    low++;
                }
                if(low!=high)
                {
                    Swap(ref list[low], ref list[high]);
                    high--;
                }
            }
            return low;
        }
    }

class Program
    {
        static void Main(string[] args)
        {
            QuickSort quick = new QuickSort();
            int[] arr = new int[] {4,5,1,9,6,3,2,8,7 };
            quick.Sort(arr, 0, 8);
            foreach (int a in arr)
            {
                Console.WriteLine(a);
            }
            Console.ReadLine();
        }
       
    }