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