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

Question

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<T> Quicksort<T>(IEnumerable<T> list) 
            where T : IComparable<T>
        {
            if ((list == null) || !list.Any())
                return Enumerable.Empty<T>();

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

            return Quicksort(smallerAndLarger.FirstOrDefault(x => x.Key < 0))
                   .Concat(new List<T>(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?

Answer 1

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 :)

Answer 2

I know it comes out a little longer-looking, but extracting a few variables made it clearer (at least to me) as to what was going on:

    private static IEnumerable<T> Quicksort<T>(IEnumerable<T> list) where T : IComparable<T>
    {
        // prevent potentially expensive multiple IEnumerable iterations
        list = list == null ? Enumerable.Empty<T>().ToList() : list.ToList();
        if (!list.Any())
        {
            return Enumerable.Empty<T>();
        }

        var head = list.First();
        var tail = list.Skip(1);
        var smallerAndLarger = tail.GroupBy(n => n.CompareTo(head)).ToList();
        var smaller = smallerAndLarger.FirstOrDefault(x => x.Key < 0);
        var larger = smallerAndLarger.FirstOrDefault(x => x.Key >= 0);

        return Quicksort(smaller).Concat(new[] { head }).Concat(Quicksort(larger));
    }

Answer 3

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

1. This is not guaranteed to split the list into two groups. In fact, your code is guaranteed not to work correctly if it contains duplicates of the first item (the pivot). For example Quicksort(new int[] { 1, 1, 2 }) will return { 1, 1 }.

   Even if you fixed this, CompareTo() is allowed to return any number, as long as its sign indicates the relation correctly. A fix would be to follow the F# version more closely:

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

   And then modify the following conditions to x => x.Key and x => !x.Key.

2. I think that using GroupBy() here makes things worse. You're already iterating the input multiple times partially (mostly due to First()), so you might as well just iterate it multiple times fully and use two Where()s for the partitions:

   var head = list.First();
   var tail = list.Skip(1);
   var smaller = tail.Where(n => n.CompareTo(head) < 0);
   var larger = tail.Where(n => n.CompareTo(head) >= 0);
   

   I think this makes it easier to see what's going on and also avoids GroupBy()-related bugs (see #1 above).

---

smallerAndLarger.FirstOrDefault(x => x.Key < 0)

When you know there is going to be one or zero matching items, you should use SingleOrDefault(), not FirstOrDefault(). That way, if you have a bug and there is more than one item, you're going to get an exception, instead of incorrect data.

---

.Concat(new List<T>(new[] { list.First() }))

Array already implements IEnumerable<T>, you don't need to copy it to a List for this. And if you did want to create a single-element list, you don't need to create an array for that: new List<T> { list.First() }.