Quick Sort

Worst case performance	O(n2)
Best case performance	O(n log n)
Average case performance	O(n log n)

(Source: http://en.wikipedia.org/wiki/Quicksort )

Tip: Randomly shuffle the array before sort to reduce the probability of the Worst case.

class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        public int[] QuickSort(int[] input)
        {
            this.QuickSort(input, 0, input.Length - 1);
            return input;
        }

        private void QuickSort(int[] input, int low, int high)
        {
            if (low < high)
            {
                int j = Partition(input, low, high);
                QuickSort(input, low, j - 1);
                QuickSort(input, j + 1, high);
            }
        }

        private int Partition(int[] input, int low, int high)
        {
            int i=low+1;
            int j = high;
            // out of the loop if low value is come to the partition point

            while (true)
            {
                while (input[i] < input[low])
                {
                    i++;
                    if (i >= high)
                    {
                        break;
                    }
                }

                while (input[j] > input[low])
                {
                    j--;
                    if (j <= low)
                    {
                        break;
                    }
                }

                if (i >= j)
                {
                    Swap(input, j, low);

                    break;
                }
                else
                {
                    Swap(input, i, j);
                }
            }

            return j;
        }



        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] Quick = new int[arraySize];
         

            for (int x = 0; x < Quick.Length; x++)
            {
                Quick[x] = x;
            }

            for (int x = 0; x < Quick.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = Quick[random];
                Quick[random] = Quick[x];
                Quick[x] = temp;
           
            }

            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.QuickSort(Quick);
            StopWtch.Stop();
            Console.WriteLine("QUICKSORT:   " + StopWtch.Elapsed.TotalSeconds + "sec");

            Console.ReadLine();
        }
    }