Quicksort is the demonstration of the divide-and-conquer strategy, which is just as useful in languages that enforce immutability as it is in languages that allow mutation.
The fact that you can update in-place is a nice bonus that gives the algorithm great performance and space characteristics in languages with mutable datastructures, but that implementation detail is not an inherent part of the beauty of the algorithm.
It's relevant because weavejester suggested quicksort is easier to implement in an imperative language.
No, the demonstration of divide-and-conquer strategy is the merge sort. The whole point of quicksort is that it is in place, which makes it fast in spite of the pessimistic quadratic time -- that's why it is called quicksort, actually. This naive implementation is neither fast, nor in place, nor quicksort.
No, the demonstration of divide-and-conquer strategy is the merge sort.
So is Quicksort. There needn't be just one algorithm that demonstrates divide and conquer.
The whole point of quicksort is that it is in place, which makes it fast in spite of the pessimistic quadratic time
That's not the whole point of quicksort. It is done in-place, but that's just a great side effect of the algorithm. But assuming a cacheless memory model (for example the RAM model) the complexity of the out-of-place version is unchanged. The great thing about QS, IMO, is that it's easy to implement and typically O(n log n). When it is quadratic it is slow -- being in-place only barely makes the quadratic version more tolerable.
With that said, I know what you're saying :-)
If you read "Purely Functional Data Structures" there are a lot of tree/graph manipulations that are cake to do in C, but are a bear in ML/Haskell. A great programmer has all tools at her disposal, not just one (even if it is finely tuned).
The fact that you can update in-place is a nice bonus that gives the algorithm great performance and space characteristics in languages with mutable datastructures, but that implementation detail is not an inherent part of the beauty of the algorithm.
It's relevant because weavejester suggested quicksort is easier to implement in an imperative language.