Could this QuickSort be made more consise and "nicer"?

After seeing this example of a "primitive" QS implementation in F# by Scott W

let rec quicksort2 = function
   | [] -> []                         
   | first::rest -> 
        let smaller,larger = List.partition ((>=) first) rest 
        List.concat [quicksort2 smaller; [first]; quicksort2 larger]

He has an example in C# which is far longer, I figured that this approach should be able to be more closely modeled than his C# example so this was my best attempt:

private static IEnumerable Quicksort(IEnumerable list) 
            where T : IComparable
        {
            if ((list == null) || !list.Any())
                return Enumerable.Empty();

            var smallerAndLarger = list.Skip(1).GroupBy(n => n.CompareTo(list.First()));

            return Quicksort(smallerAndLarger.FirstOrDefault(x => x.Key (new[] { list.First() }))
                   .Concat(Quicksort(smallerAndLarger.FirstOrDefault(x => x.Key >= 0)));
        }

Now depending on how you count my solution is "equally" short as the F# one. But it does have more noise, that I cannot argue with. I wonder, can it be made clearer and perhaps even shorter than this?

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 => 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 & \text{Equal} & \text{Alternating} & \text{Sorted} & \text{Reverse sorted} \\
\hline
10,000 & 7.9\text{s} & 1.8\text{s} & 7.8\text{s} & 7.7\text{s} \\
100,000 & \text{N/A} & \text{N/A} & \text{N/A} & \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 & \text{Equal} & \text{Alternating} & \text{Sorted} & \text{Reverse sorted} \\
\hline
100,000 & 4\text{ms} & 5\text{ms} & 2\text{ms} & 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 :)

StackExchange Code Review Q#69650, answer score: 4