Could this QuickSort be made more consise and "nicer"?
I'm more worried about the efficiency than conciseness.

Here are some sample inputs:


Equal new int[n]
Alternating Enumerable.Range(0, n).Select(x =&gt; x % 2).ToArray()
Sorted Enumerable.Range(0, n).ToArray()
Reverse sorted Enumerable.Range(0, n).Reverse().ToArray()


\begin{array}{ r | r | r | r | r }
 n &amp; \text{Equal} &amp; \text{Alternating} &amp; \text{Sorted} &amp; \text{Reverse sorted} \\
\hline
  10,000 &amp; 7.9\text{s} &amp; 1.8\text{s} &amp; 7.8\text{s} &amp; 7.7\text{s} \\
  100,000 &amp; \text{N/A} &amp; \text{N/A} &amp; \text{N/A} &amp; \text{OOM} \\
\end{array}

N/A is where I gave up waiting after a minute.

By comparison, Array.Sort on the same machine:

\begin{array}{ r | r | r | r | r }
 n &amp; \text{Equal} &amp; \text{Alternating} &amp; \text{Sorted} &amp; \text{Reverse sorted} \\
\hline
  100,000 &amp; 4\text{ms} &amp; 5\text{ms} &amp; 2\text{ms} &amp; 3\text{ms} \\
\end{array}

One advantage of QuickSort is that it can be done in-place, which is not happening here. If you're OK with allocating more memory, why not use Merge sort with its worst-case \$O(n \log n)\$ time guarantee?

Another issue is the choice of the pivot. Choosing the first element will give quadratic performance for sorted inputs. One option is to shuffle the input array before sorting; another is to choose the pivot at random (these are not the only options).

Robert Sedgewick* has a great page on QuickSort which touches on a lot of implementation issues. He also has a couple of implementations in Java, which translate easily to C#.

*Who did his Ph.D on QuickSort under Don Knuth, so well worth listening to :)