Glenn G. Chappell [EMAIL PROTECTED] writes
I am wondering about a design decision in the List module.
To wit: sort, in both the H98 library report and the Hugs file
List.hs, is implemented using a quadratic sort (insertion sort).
Using the name sort certainly suggests that this is a good function
to use for sorting. I would think it is pretty obvious that sort
should be implemented using an efficient algorithm. I am thinking
primarily of merge sort, which has O(n log n) worst case behavior,
is stable, and has an elegant and efficient functional implementation.
Certainly insertion sort is good to have around, if one is sorting
data that is nearly sorted already, but I would say insertion sort
is clearly not the best choice (or even a good choice) for a general-
purpose sorting algorithm.
Or am I missing something?
The Standard library specifies only the map related to the name
`sort'. This map can be described, for example, via sort-by-insertion
program.
And the algorithm choice is a matter of each particular
implementation. Implementation has right to change the algorithm.
For example, I tried once to argue with GHC for incorporating the
mergeSort algorithm for `sort'.
But they have some version of quickSort which is said faster on
average and O(n^2) in the worst case.
Disliking this n^2 hazard, I overload `sort' with my_sort.
-
Serge Mechveliani
[EMAIL PROTECTED]
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
