|
Correct me if I am wrong but they are actually using mergesort (mergeAll) as it is significantly faster in Haskell than in-place quicksort (qsort). That means there is a lot of overhead for doing something simple like an in-place qsort that should be much faster than a mergesort. I am at a loss on why the provided code is any more elegant than:
http://en.literateprograms.org/Merge_sort_%28C_Plus_Plus%29 or this (also taken from rosetta code)? #include <iterator>
#include <algorithm> // for std::partition
#include <functional> // for std::less
template<typename RandomAccessIterator,
typename Order>
void quicksort(RandomAccessIterator first, RandomAccessIterator last, Order order)
{
if (last - first > 1)
{
RandomAccessIterator split = std::partition(first+1, last, std::bind2nd(order, *first));
std::iter_swap(first, split-1);
quicksort(first, split-1, order);
quicksort(split, last, order);
}
}
template<typename RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last)
{
quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}
The above code is more verbose? |
Well, the problem not so much that there is a lot of overhead for doing an in-place qsort. The problem is that "in-place" anything is impossible in Haskell, it violates referential transparency.
Merge sort however needs no in-place update and can trivially (in Haskell world) be parallelized (merge sort is associative, you can use it as the reduce step of MapReduce). So you are correct in concluding that mergesort is used in Haskell.
You state "something simple like an in-place qsort", your statement about qsort being simple makes some assumptions about your programming languages world, which are not the same for all languages especially not Haskell. No whether all this is a pro and a con depends on what sort of coding you're doing of course.
I think that people call Haskell's code more elegant because they (like me) find C++ template and type annotations to be annoyingly verbose and messy for no good reason. For example for the two quicksort functions:
"template<typename RandomAccessIterator> void quicksort(RandomAccessIterator first, RandomAccessIterator last)"
vs
"quicksort :: (Ord a) => [a] -> [a]" (where "Ord a" means that a is an instance of the typeclass of ordered items).