At 15:04 -0400 98/05/07, S. Alexander Jacobson wrote:
>You recursively partition the list based on the first character not
>already processed. So if you have a list like:
>
>[alex,fergus,robert,allen,frank,ralf]
>
>At the next stage you have:
>[(a,[alex,allen]),(f,[fergus,frank]),(r,[robert,ralf])]
It seems me that it ought to be faster and simpler to just view this as a
set with a lexicographical ordering and use the most efficient sorting
algorithm for that, more general, situation.
Algorithms of sorting time O(n^2) generally have less over-head than O(n
log n) algorithms, and are faster for smaller sets. Quicksort has average
time O(n log n), but worst case O(n^2), for example if the list is already
nearly sorted. There are more advanced algorithms improving on this problem.
Perhaps Haskell ought to include some optimized hardwired sorting
algorithms for lists of ordered types. After all, if one is just interested
in getting the list sorted, one is not going to be very interested in
writing a complicated sorting algorithm.
Hans Aberg
* Email: Hans Aberg <mailto:[EMAIL PROTECTED]>
* Home Page: <http://www.matematik.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
