Quicksort Algorithm implementation in C#

Since begining of January 2012, I  tried  spend some spare time of studying  computer science base. Sure,  of course, I know  a lot  from that, but not  all. In addition, it is useful to repeat the basics knowledge.  I decided  create my own library of algorithm and data structures,  not  for  production   using but  for studying and understanding them.  I spent a lot of time  surfing internet  for good articles  regarding  algorithms and data structures. 

Today, I would like to  talk  about QuickSort algorithm. 

Quicksort, like lots of others sort algorithms, applies the divide-and-conquer paradigm. 

Here is the three-step divide-and-conquer process for sorting a

typical subarray Arr[q..w]

• Divide: Partition (rearrange) the array Arr[q..w] into two subarrays  Arr[q..e-1] and  Arr[e+1..w] such that each element of Arr[e..w-1] is less than or equal to Arr[e] which is, in turn, less than or equal to each element of Arr[e+1,w]. Compute the index e as part of this partitioning procedure. 
• Conquer: Sort the two subarrays Arr[q..e-1] and Arr[e+1..w] by recursive calls to quicksort.
• Combine: Because the subarrays are already sorted, no work is needed to combine them: the entire array Arr[q..w] is now sorted.

The quicksort algorithm has a worst-case running time of O(N^2) on an input array of n numbers. Despite this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is O(n lg n), and the constant factors hidden in the O(n lg n) notation are quite small.

Here is my C# implementation using recursion:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SortComparison { class QuickSort<T>; where T :IComparable; { private static T[] A; public static void Sort(T[] arr) { A = arr; InnerSort(0, A.Length - 1); } private static void InnerSort(int low, int high) { int i = low; int j = high; T pivot = A[(low + high) / 2]; do { while (A[i].CompareTo(pivot) < 0) i++; while (A[j].CompareTo(pivot) > 0) j--; if (i <= j) { T tmp = A[i]; A[i] = A[j]; A[j] = tmp; i++; j--; } } while (i <= j); if(i < high) InnerSort(i,high); if(low < j) InnerSort(low,j); } } }

As you  can see  it quit trivial  implementation,  but very efficient.