How slow are functional implementations of quicksort?

I’ve been talking with my colleague Jakub Skoczen.  He’s insisting that functional implementations of quicksort, which make and return new arrays at each level of recursion, must surely be much slower than imperative implementations that modify an array in place.

And I can see his point.

What does it take to test a sorting routine?

Thanks to all of you who have taken part in yesterday’s selection-sort challenge, and everyone who’s still submitting code.  (If you haven’t yet done so but plan to, then please don’t read this article until you’ve written your code according to the rules laid down in that article, otherwise you’ll see hints that you probably don’t want to see up front.)

I promised yesterday that I’d post some ideas about a test-suite in a subsequent article: this is it.

Another challenge: can you write a correct selection sort?

A month ago today, I posted what’s turned out to be by far the most commented-on article on this site: Are you one of the 10% of programmers who can write a binary search?.  The gist of it was that Jon Bentley, in his book Programming Pearls [amazon.com, amazon.co.uk], had found in many seminars that when professional programmers are given a high-level description of the binary-search algorithm and a couple of hours to write code that implements it, only one in ten of the offered solutions are free of bugs. An amazing number of you attempted the challenge — somewhere around 500 — and the results seemed to show a correctness rate somewhere between 10% and 50%.

Now we’re going to try the same exercise with one of the simplest of sorting algorithms: selection sort.  (No Wikipedia link for now, because you might see information that you don’t want to see yet.)