The first “homework assignment” of Dr. Erik Meijer’s functional programming course on Channel 9 was to write quicksort using C# (or VB) functional comprehensions. I did it in a very naïve way, then I wondered if I could get a “free” speed up simply by leveraging some of the Parallel Extensions to .NET 4.0.
My results were mixed. As the number of integers in the unsorted array increases, the parallel implementation begins to pull away, but with smaller numbers the sequential implementation is faster. I think I’ll try to do something very similar in Erlang this weekend. It should be an interesting comparison exercise since Erlang terms are immutable. A naïve implementation should look pretty similar I think. Neither of them would be true quicksort implementations, since the algorithm was specified by Hoare to work in a mutable fashion with the original array being changed in situ.
My dual core machine yielded times of about 80s and 100s when sorting an array of a thousand for the parallel (QsortP) and sequential (Qsort) methods respectively. So that’s definitely not impressive, but I did it in a very abstract way. The same function could sort strings or floats or anything else that implements IComparable.